3..
Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.
Realizacje algorytmu Przegląd zupełny Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa algorytmu wyniesie co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi ponieważ jest tyle możliwych ciągów zero-jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona), podstawiając za, a i b jedynki.
Rozwiązania dynamiczne Problem plecakowy może być rozwiązany w czasie pseudowielomianowym przy użyciu programowania dynamicznego. Rozwiązanie podane poniżej dotyczy przypadku, w którym można użyć wielokrotnie każdego elementu:
Niech będą wagami poszczególnych elementów oraz ich wartościami. Algorytm ma zmaksymalizować sumę wartości 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 jest rozwiązaniem problemu.
jest zdefiniowane rekurencyjnie: