Viene descritta di seguito la soluzione per il ''problema dello zaino senza limiti''.
Si indichino con <math>c_1,\dots,c_nc_N</math> i guadagni offerti dagli oggetti, e con <math>w_1,\dots,w_nw_N</math> i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo che il peso complessivo sia inferiore o uguale al peso massimo consentito <math>W</math>. Ora, si indichi con <math>A(k)</math> il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore od uguale ad <math>k</math>. Ovviamente <math>k\leq W</math>, e <math>A(W)</math> sarà la soluzione del nostro problema.
Si definiscono gli <math>A(k)</math> ricorsivamente come di seguito:
Qui si considera zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da <math>A(0)</math> fino a <math>A(W)</math> si ottiene la soluzione. Dato che il calcolo di ogni <math>A(k)</math> implica l'esame di <math>nN</math> oggetti (che sono tutti stati calcolati in precedenza), e visto che ci sono <math>W</math> valori di <math>A(k)</math> da calcolare, il tempo impiegato per trovare la soluzione è <math>O(nWNW)</math>.
Ciò non contraddice il fatto che il problema dello zaino è [[NP-completo]], dato che <math>W</math>, al contrario di <math>nN</math>, non è polinomiale rispetto alla lunghezza dell'input del problema. Tale lunghezza è proporzionale al numero di bit in <math>W</math>, e non a <math>W</math> stesso.
