Problema dello zaino: differenze tra le versioni

Si indichino con <math>c_1,\dots,c_n</math> i guadagni offerti dagli oggetti, e con <math>w_1,\dots,w_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(i)</math> il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore od uguale ad <math>i</math>. Ovviamente <math>i\leq W</math>, e <math>A(W)</math> sarà la soluzione del nostro problema.