Wpisany przez Tomasz Lubiński
niedziela, 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ę:
przy założeniu:
, 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:
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
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
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ę:
przy założeniu:
, 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:
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
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 |
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Michał Knasiecki | C/C++ |  | |
  / 1 | |
| Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 |  | |
/ 1 |
Poprawiony: czwartek, 09 czerwca 2011 21:02