Problema dello zaino: differenze tra le versioni

Il '''Problemaproblema dello zaino''', detto anche '''''Knapsack problem''''', è un problema di ottimizzazione combinatoria posto nel modo seguente:.

:siaSia dato uno [[zaino]] che possa sopportare un determinato peso. Siano dati inoltre ''<math>N''</math> oggetti, ognuno dei quali caratterizzato da un ''peso'' e un ''valore''. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

:* ognuno degli ''<math>N''</math> oggetti possiede un peso <math>w_i</math> e un valore <math>c_i</math>;

:* si indica con ''<math>W''</math> il peso massimo sopportabile dallo zaino;

:* la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere <math>x_i</math>.

: <math>\max Z = \sum_{i=1}^N c_i\cdot x_i.</math>

: <math>\sum_{i=1}^N w_i\cdot x_i\leq W.</math>

:* '''problema dello zaino 0-1''':

:: <math>x_i=\left\{0,1\right\} \quad \forall i=1,...\ldots,N,</math>

:* '''problema dello zaino con limiti'''

:: <math>x_i \leq b_i \quad \forall i=1,...\ldots,N,</math>

:* '''problema dello zaino senza limiti'''

:: <math>x_i \in \N \quad \forall i=1,...\ldots,N,</math>

Il problema dello zaino è risolto spesso usando la [[programmazione dinamica]], anche se è noto che tale metodo abbia un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema [[NP-difficile]], e questo ha indirizzato la ricerca verso il problema [[Subset-sum]] come base per il sistema di [[Public key infrastructure|crittografia a chiave pubblica]], come [[Merkle-Hellman]]. Questi tentativi usavano tipicamente alcuni [[Gruppo (matematica)|gruppi]] oltre agli interi. [[Merkle-Hellman]] e altri algoritmi simili vennero presto abbandonati, in quanto i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.

Si indichino con <math>c_1,\dotsldots,c_N</math> i guadagni offerti dagli oggetti, e con <math>w_1,\dotsldots,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(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.

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

* <math>A(k)=\max \lbrace c_j + A(k - w_j) | w_j \le k \rbrace. </math>.

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

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

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

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

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in <math>[0, 1]</math> delle variabili <math>x_i</math> (in particolare una sola variabile avrà valore non binario). In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.