Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla aż do pozwala obliczyć wynik. Ponieważ obliczenie wymaga sprawdzenia elementów, a wartości do obliczenia jest złożoność obliczeniowa programu wynosi
Powyższa złożoność nie neguje faktu, że problem plecakowy jest NP-zupełny, ponieważ w przeciwieństwie do nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do liczby bitów w liczbie a nie do wartości
Pseudokod (rozwiązanie znajduje się w komórce A[W], tablica A[0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n]): for i:=0 to W do A[i]:= 0
for i:=0 to W do for j:=1 to n do if ( w[j] <= i ) then //sprawdzenie czy j-ty element mieści się w plecaku o rozmiarze i A[i] = max(A[i], A[i-w[j]] + c[j])
Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech będzie wagą elementów oraz wartościami. Algorytm ma zmaksymalizować wartość elementów przy zachowaniu sumy ich wagi mniejszej bądź równej Niech będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej i wykorzystaniu pierwszych elementów.