|
Written by Tomasz Lubiński
|
|
Sunday, 31 July 2005 23:41 |
|
There are no translations available.
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
| 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 |
Czyli należy wziąć 3 kontenery 4-tego typu i 1 3-ego typu.
.
|
|
Last Updated on Saturday, 29 May 2010 16:57 |
algorytm.org 
Tools 
