Problema dello zaino: differenze tra le versioni

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(CW)</math> si ottiene la soluzione. Dato che il calcolo di ogni <math>A(i)</math> implica l'esame di <math>n</math> oggetti (che sono tutti stati calcolati in precedenza), e visto che ci sono <math>CW</math> valori di <math>A(i)</math> da calcolare, il tempo impiegato per trovare la soluzione è <math>O(nCnW)</math>.

Ciò non contraddice il fatto che il problema dello zaino è [[NP-completo]], dato che <math>CW</math>, al contrario di <math>n</math>, non è polinomiale rispetto alla lunghezza dell'input del problema. Tale lunghezza è proporzionale al numero di bit in <math>CW</math>, e non a <math>CW</math> stesso.