On 24 Gru, 11:45, "bagno" <b...@o...pl> wrote:
> Mariusz Marsza kowski wrote:
> >> No jak o co chodzi ? Staramy si doprowadzi do sytuacji, e w ka dym
> >> pojemniku jest nie wi cej ni LIMIT kulek. Je eli wsz dzie jest za
> >> du o to niczego nie zmieniamy, tak samo je eli wsz dzie jest
> >> poni ej. Przenosimy tylko tak eby nie przekroczy maksymalnego
> >> kosztu pojedy czego przeniesienia.
> >> Najlepiej zacz od pojemnika gdzie jest najwi cej i przenosi tam
> >> gdzie jest najmniej (przy zachowaniu tego maksymalnego kosztu
> >> przeniesienia).
> > Czyli nie chodzi o uzyskanie minimalnego acznego kosztu, ale o to czy
> > zadanie da sie rozwiazac nie przeraczajac ani razu maksymalnego
> > kosztu?
>
> Ju sam si w tym gubie.
Nadal nie mam 100% pewnosci :)
Moze ja zdfinuje.

Mamy N wiader ustawionych w szeregu. W wiadrach leżą kulki. Każde
wiadro ma maksymalny limit ilości kulek. Jeśli kulek jest mniej niż
limit, to koszt przetrzymywania w nim kulek jest równy zero. Jeśli
kulek jest więcej niż limit, to koszt przetrzymywania jest dany
funkcją
F_i(x), gdzie i to numer wiadra, a x to ilość kulek o jaką został
przekroczony limit. Każda F_i jest dodatnia w calej dziedzinie.

Przeniesienie kulki z jednego wiadra do drugiego wiąże się z dodatnim
kosztem proporcjonalnym do odległości pomiędzy jednym wiadrem a
drugim.

Każda kulka ma przypisany limit. Po przeniesieniu kulki na odległość
X wiader, od jej limitu jest odejmowana wartość X. Nie można
doprowadzić
do sytuacji, aby limit jakiejś kulki spadł poniżej zera.

Chodzi o to, aby znaleźć taki sposób przenoszenia kulek, aby suma
kosztów przetrzymywania F_i(X) + suma kosztów przenoszenia była
minimalna?

Pozdrawiam