Mamy dany zbiór n przedmiotów oraz dla każdego z nich określoną wartość v[i] i ciężar w[i]. Naszym zadaniem jest wpakowanie przedmiotów o jak największej wartości (ilość się nie liczy) do plecaka. Mamy jednak ograniczenie - jesteśmy w stanie udźwignąć co najwyżej ciężar b.
Niech stan będzie określony przez parę liczb (i,j). Powiedzmy, że chcemy skorzystać jedynie z pierwszych i przedmiotów, choć nie koniecznie wszystkich (pozostałymi na razie się nie przejmujmy) i za ich pomocą utworzyć zbiór przedmiotów o wadze dokładnie j. Wybierzmy sobie najbardziej wartościowy, ze zbiorów spełniających te warunki. Suma wartości przedmiotów z tego zbioru jest wartością funkcji stanu V(i,j).
No to czas na zależności między stanami. Gdy chcemy obliczyć
V(i,j) musimy znać pewne wartości V(i-1,?).
Czyli chcemy obliczyć najwartościowszy zbiór i-elementowy
(chodzi mi o zbiór złożony z pierwszych i przedmiotów)
o ciężarze dokładnie j. Mamy już obliczone najwartościowsze
zbiory (i-1)-elementowe. Zatem zastanawiamy się czy dodać
i-ty przedmiot (o wadze w[i] i wartości v[i])
do pewnego (i-1)-elementowego zbioru, czy też nie.
Załóżmy, że chcemy ten przedmiot użyć. Żeby skonstruować zbiór o ciężarze
dokładnie j musimy dodać go do zbioru o ciężarze
j-w[i] (chyba, że j-w[i]<0, to wtedy ta możliwość
odpada), którego największa możliwa wartość jest równa
V(i-1,j-w[i]). Nowy zbiór skonstruowany w ten sposób będzie
miał wartość o V[i] większą. Zatem
V(i,j)=V(i-j,j-w[i])+v[i].
Może się jednak okazać, że wcale nie jest lepiej brać pod uwagę
ten i-ty przedmiot, bo (i-1)-elementowy zbiór o wadze
j może się okazać wartościowszy. W takim przypadku
V(i,j)=V(i-1,j). Żeby dowiedzieć jaką wartość ma mieć
V(i,j) należy po prostu wybrać większą z wartości:
V(i-1,j) i V(i-j,j-w[i])+v[i]
(jak już wspomniałem, w niektórych przypadkach możliwa jest tylko
ta druga opcja).
Jeśli chodzi o stany początkowe, to V(0,0)=0, natomiast
V(0,x>0) ma wartość nieokreśloną (można przyjąć
-nieskończoność). Oznacza to tyle, że żądany ciężar nie jest
osiągalny przez wybrane przedmioty.
W praktyce chodzi o to, że gdy do obliczenia jakiegoś V(i,j)
mamy do wyboru skorzystanie ze stanu z wartością określoną i z wartością
nieokreśloną, to musimy wybrać ten pierwszy. Jeżeli obie wartości byłyby
nieokreślone, to V(i,j) też takie ma być.
Wynik, którego szukamy to maksymalna z wartości: V(n,0), V(n,1), ..., V(n,b). Dlatego bierzemy maxa z stanów, a nie samo V(0,b), ponieważ wcale nie musimy wypychać plecaka ciężarem dokładnie b - czasem może okazać się to niewykonalne, a czasem po prostu nieopłacalne.
Każdemu stanowi (i,j) odpowiada element w tablicy V[i,j],
który jest równy V(i,j). Teraz mając dane pewne stany początkowe
możemy wypełnić całą tablicę. Musimy to jednak robić w odpowiedniej
kolejności. Jest to bardzo ważne, bo żeby wypełnić komórkę V[i,j]
musimy znać pewne komórki V[i-1,?].
Zatem znając zerowy wiersz tej tablicy V[0,?] (bo są to stany
początkowe) możemy wyliczyć elementy V[1,0], V[1,1], ..., V[1,b],
czyli pierwszy rząd tablicy. A z tego można wyliczyć drugi, później
trzeci, itd.
Powiem więcej. Skoro za każdym razem korzystamy z jedynie z
poprzedniego wiersza tablicy, to po co trzymać pozostałe?
Otóż można ograniczyć się jedynie do jednej tablicy jednowymiarowej.
Mając wartości V[0..b] odpowiadające pewnemu
i-temu wierszowi, możemy wyliczać sobie wartości dla kolejnego
wiersza i wpisywać je do tej samej tablicy, tak że w jednej tablicy
V znajduje się mieszanka wartości z dwóch wierszy.
Tu jednak należy uważać - wartości należy wyliczać od tyłu (poczynając
od V[b]). Gdybyśmy robili to od przodu, to zamazalibyśmy
sobie wartości, z których musimy w przyszłości skorzystać.
To wersja z tablicą dwuwymiarową:
{n -liczba przedmiotow;
b - max. ciezar;
v[1..n] - tablica wartosci przedmiotow;
w[1..n] - tablica ciezarow przedmiotow;
V[0..n,0..b] - tablica stanow}
{wpisywanie stanow poczatkowych}
V[0,0]:=0;
for i:=1 to b do
V[0,i]:=-1; {wartosc ujemna bedzie oznaczac stan nieokreslony}
{algorytm wlasciwy}
for i:=1 to n do
for j:=0 to b do
if (j-w[i]<0)or(V[i-1,j-w[i]]<0) then
{jezeli waga jest ujemna, lub dla tej wagi jest stan nieokreslony...}
V[i,j]:=V[i-1,j] {to nie korzystamy z i-tego przedmiotu}
else
{w przecinym wypadku wybieramy czy lepiej skorzystac, czy nie}
V[i,j]:=max(V[i-1,j-w[i]]+v[i],V[i-1,j]);
{wynik jest najwieksza z wartosci V[n,0..b]}
Wersja z tablicą jednomiarową:
{n -liczba przedmiotow;
b - max. ciezar;
v[1..n] - tablica wartosci przedmiotow;
w[1..n] - tablica ciezarow przedmiotow;
V[0..b] - tablica niektorych stanow}
{wpisywanie stanow poczatkowych}
V[0]:=0;
for i:=1 to b do
V[i]:=-1; {wartosc ujemna bedzie oznaczac stan nieokreslony}
{algorytm wlasciwy}
for i:=1 to n do
for j:=b downto 0 do
if not((j-w[i]<0)or(V[j-w[i]]<0)) then
{jezeli waga nie jest ujemna ani dla tej wagi nie jest stan nieokreslony...}
{wybieramy czy lepiej skorzystac z przedmiotu, czy nie}
V[j]:=max(V[j-w[i]]+v[i],V[j]);
{w przeciwnym wypadku zostaje wartosc jaka byla -
co znaczy, ze przedmiotu nie wybrano}
{wynik jest najwieksza z wartosci V[0..b]}
Właściwie to mamy dwie pętle (jedna w drugiej), które w każdym z n*b przebiegów robią coś w czasie stałym. Stąd złożoność algorytmu jest O(n*b). Ale nie jest to czas wielomianowy (a pseudowielomianowy). Zauważmy, że znacznie zwiększając parametr b znacznie powiększa się czas wykonywania algorytmu, a rozmiar instancji zwiększa się minimalnie (przypominam, że rozmiar instancji to wielkość zakodowanych wszystkich danych wejściowych). Czyli złożoność czasowa zdecydowanie nie zależy wielomianowo od rozmiaru instancji.