Wpisany przez Tomasz Lubiński,
31 lipca 2005 23:41
Algorytm jest oparty o metodę programowanie dynamiczne
Problem załadunku jest pewną odmianą problemu plecakowego. Tu również mamy pewne elementy (kontenery), którym jest przypisany cięzar i pojemność. Jest danych n-typów kontenerów, gdzie dla j-tego typu a[j] oznacza jego ciężar a c[j] jego pojemność. Tak jak w problemie plecakowym daną mamy również ładowność, którą oznaczymy jako b. Cała różnica polega na tym, że podczas załadunku możemy użyć dowolnej ilości elementów danego typu j (a nie jak w problemie plecakowym jednego). W problemie tym chodzi o to by maksymalizować funkcję:
By rozwiązać ten problem stosując programowanie dynamiczne posłużymy się oprócz tablic jednowymiarowych a - tablica ciężarów elementów i c - tablica pojemności elementów, również dwoma tablicami dwuwymiarowymi f i x o rozmiarach n na b. Najpierw przeprowadzimy pierwszą; iterację dla l = 0,1, ..., b do wzorów:
Po tych operacjach możemy już odczytać wynik z tablic f oraz x. A więc odczytujemy wartość elementu położonego na samym końcu w ostatniej kolumnie tablicy x. Wartość ta to numer kontenera który musimy zabrać, a więc zwiększamy w[ta_wartość] o jeden, i idziemy w górę tej kolumny o cięzar tego elementu czyli a[ta_wartość], odczytujemy wartość tego elementu i postępujemy analogicznie jak w poprzedniej sytuacji (zwiększamy odpowiednie w[j] o jeden i idziemy w górę). Czynności powtarzamy tak długo aż jako numer kontenera nie pojawi się nam zero.
dla b=9
Czyli należy wziąć 3 kontenery 4-tego typu i 1 3-ego typu.
Problem załadunku jest pewną odmianą problemu plecakowego. Tu również mamy pewne elementy (kontenery), którym jest przypisany cięzar i pojemność. Jest danych n-typów kontenerów, gdzie dla j-tego typu a[j] oznacza jego ciężar a c[j] jego pojemność. Tak jak w problemie plecakowym daną mamy również ładowność, którą oznaczymy jako b. Cała różnica polega na tym, że podczas załadunku możemy użyć dowolnej ilości elementów danego typu j (a nie jak w problemie plecakowym jednego). W problemie tym chodzi o to by maksymalizować funkcję:
w_1c_1 + w_2c_2 + ... + w_nc_n
przy założeniu:
w_1a_1 + w_2a_2 + ... + w_na_n \leq b
czyli suma załadowanych kontenerów musi być mniejsza lub równa ładowności, gdzie w[j] to liczba załadowanych kontenerów j-tego
typu (w[j]≥0). By rozwiązać ten problem stosując programowanie dynamiczne posłużymy się oprócz tablic jednowymiarowych a - tablica ciężarów elementów i c - tablica pojemności elementów, również dwoma tablicami dwuwymiarowymi f i x o rozmiarach n na b. Najpierw przeprowadzimy pierwszą; iterację dla l = 0,1, ..., b do wzorów:
f_{1}(l)=c_{1}\lfloor\frac{l}{a_{1}}\rfloor
x_{1}(l)=\begin{cases}0 & \text{ dla } f_{1}(l) = 0 \\ 1 & \text{ dla } f_{1}(l) > 0\end{cases}
Mamy już teraz wypełnione pierwsze kolumny w tablicach f oraz x. Teraz musimy skonstruować zagnieżdżoną iterację. Wewnątrz pętli dla j = 2,3, ..., n umieszczamy jeszcze jedną pętlę dla l = 0,1, ..., b i wewnątrz niej wykonujemy następujące działania
f_{j}(l) = max\left\{f_{j-1}(l), f_{j-1}(l-a_{j})+c_{j}\right\}\text{, dla }l<0\text{ }f_{j}(l)=-\infty
x_{j}(l)=\begin{cases}x_{j-1}(l) & \text{ dla } f_{j-1}(l) > f_{j}(l-a_{j})+c_{j} \\ j & \text{ dla } f_{j-1}(l) \leq f_{j}(l-a_{j})+c_{j} \end{cases}
Po tych operacjach możemy już odczytać wynik z tablic f oraz x. A więc odczytujemy wartość elementu położonego na samym końcu w ostatniej kolumnie tablicy x. Wartość ta to numer kontenera który musimy zabrać, a więc zwiększamy w[ta_wartość] o jeden, i idziemy w górę tej kolumny o cięzar tego elementu czyli a[ta_wartość], odczytujemy wartość tego elementu i postępujemy analogicznie jak w poprzedniej sytuacji (zwiększamy odpowiednie w[j] o jeden i idziemy w górę). Czynności powtarzamy tak długo aż jako numer kontenera nie pojawi się nam zero.
Przykład:
dla b=9
| typ (j) | 1 | 2 | 3 | 4 |
| ciężar (a[j]) | 7 | 4 | 3 | 2 |
| pojemność (c[j]) | 17 | 10 | 8 | 6 |
| l | f[1,l] | f[2,l] | f[3,l] | f[4,l] | x[1,l] | x[2,l] | x[3,l] | x[4,l] |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 4 |
| 3 | 0 | 0 | 8 | 8 | 0 | 0 | 3 | 3 |
| 4 | 0 | 10 | 10 | 12 | 0 | 2 | 2 | 4 |
| 5 | 0 | 10 | 10 | 14 | 0 | 2 | 2 | 4 |
| 6 | 0 | 10 | 16 | 18 | 0 | 2 | 3 | 4 |
| 7 | 17 | 17 | 18 | 20 | 1 | 1 | 3 | 4 |
| 8 | 17 | 20 | 20 | 24 | 1 | 2 | 2 | 4 |
| 9 | 17 | 20 | 24 | 26 | 1 | 2 | 3 | 4 |
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Michał Knasiecki | C/C++ | .cpp | .cpp | ***** / 1 | |
| Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 1 |
Poprawiony: 26 sierpnia 2012 08:56