jest rozwiązaniem problemu.
Funkcja definiowana jest rekurencyjnie:
jeśli jeśli
Rozwiązaniem problemu jest wynik dla Do efektywnego wykonania algorytmu używa się tablicy do zapamiętywania obliczonych podproblemów. Złożoność obliczenia wynosi podobnie jak wyżej podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu
Pseudokod (tablica A[1..n,0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n], rozwiązanie znajduje się w komórce A[n,W]): for i:=0 to n do A[i,0]:= 0 for j:=0 to W do A[0,j]:= 0
for i:=1 to n do //rozważanie kolejno i pierwszych przedmiotów for j:=0 to W do if ( w[i] > j ) then //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j A[i,j] = A[i-1,j] else A[i,j] = max(A[i-1,j], A[i-1,j-w[i]] + c[i])
Algorytm aproksymacyjny mały|300px|W pierwszej części algorytmu zachłannego przedmioty są sortowane według stosunku wartości do wagi (po lewej), po czym wybierane są kolejno od góry te elementy które się jeszcze mieszczą w plecaku. W wyniku wybrane zostały przedmioty o 1. i 3. o łącznej wartości 11$ i wadze 11 kg. Optymalnym wynikiem byłyby jednak przedmioty 1. i 5.