Problema dello zaino: differenze tra le versioni

Versione delle 10:13, 21 feb 2008

Versione delle 18:31, 21 feb 2008

Riga 68:

* <math>A(i, 0) = 0</math>,

* <math>A(i,j) = A(i - 1, j)</math> se <math>c_i > j</math>,

* <math>A(i,j) = \max \lbrace A(i - 1, j), v_i + v_i, A(i - 1, j - c_i) \rbrace </math> se <math>c_i\le j</math>.

La soluzione può essere allora trovata calcolando <math>A(n,C)</math>. Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impieghera quindi un tempo proporzionale a <math>O(nC)</math> e uno spazio anch'esso proporzionale a <math>O(nC)</math>, anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a <math>O(C)</math>.