algorytm.org

Problem załadunku

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problem załadunku
Ocena użytkowników:***** / 15
SłabyŚwietny 
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ę:
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
Czyli należy wziąć 3 kontenery 4-tego typu i 1 3-ego typu.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 sierpnia 2012 08:56
Dodaj komentarz