Versione delle 14:00, 16 mar 2008 modifica Alez (discussione \| contributi) 1 297 modifiche m Non credo si possa più considerare uno stub ← Differenza precedente		Versione delle 14:04, 16 mar 2008 modifica annulla Alez (discussione \| contributi) 1 297 modifiche mNessun oggetto della modifica Differenza successiva →
Riga 68: * <math>A(i,j) = \max \lbrace A(i - 1, j), A(i - 1, j - c_i) + v_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~~impiegherà 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>. == Algoritmo Greedy ==

Problema dello zaino: differenze tra le versioni