|
Il '''problema dello zaino''', detto anche '''''Knapsack problem''''', è un problema di [[Ottimizzazione (matematica)|ottimizzazione]] [[calcolo combinatorio|combinatoria]] posto nel modo seguente.
:Sia dato uno [[zaino]] che possa sopportare un determinato [[peso]]. Sianoe datisiano inoltredati <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.
== Introduzione ==
:: <math>x_i \leq b_i \quad \forall i=1,\ldots,N,</math>
: ogni oggetto non può apparire nello zaino piùfino dia un certo numero di volte;
* '''problema dello zaino senza limiti'''
: ogni oggetto può apparire nello zaino un numero arbitrario di volte.
Il problema dello zaino è risolto spesso usando la [[programmazione dinamica]], anche se è noto che talequesto metodo abbiaha 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 quantopoiché i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.
La versione decisionale di questo problema è [[NP-completo|NP-completa]] e infatti è uno dei [[21 problemi NP-completi di Karp]].
Il problema dello zaino, nella versione di ottimizzazione, è di fondamentale importanza in quanto, perpuò molteessere istanzerisolto diin comunemaniera applicazione,soddisfacente puòin esseremolti risoltocasi indi manieracomune soddisfacenteapplicazione; infatti per questo problema, infatti, sono disponibili buone euristiche e buoni rilassamenti. Un algoritmo di enumerazione implicita, (ad esempio [[Branch and bound]]), normalmente non impiega molto tempo per risolverlo.
== Soluzione problema dello zaino senza limiti==
Viene descritta di seguito la soluzione per il ''problema dello zaino senza limiti''.
Si indichino con <math>c_1,\ldots,c_N</math> i guadagni offerti dagli oggetti, e con <math>w_1,\ldots,w_N</math> i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo chemantenendo il peso complessivo sia inferioreminore o uguale al peso massimo consentito <math>W</math> (vincolo). Ora, siSi 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 ada <math>k</math>. Ovviamente <math>k\leq W</math>, e <math>A(W)</math> saràè la soluzione del nostro problema.
Si definiscono gli <math>A(k)</math> ricorsivamente come di seguito:
* <math>A(k)=\max \lbrace c_j + A(k - w_j) | w_j \le k \rbrace. </math>
Quiavendo si consideraconsiderato zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da <math>A(0)</math> fino a <math>A(W)</math> si ottiene la soluzione. Dato che il calcolo di ogni <math>A(k)</math> implica l'esame di <math>N</math> oggetti (che sono, tutti stati calcolati in precedenza), e visto che ci sono <math>W</math> valori di <math>A(k)</math> da calcolare, il tempo impiegato per trovare la soluzione è <math>O(NW)</math>.
Ciò non contraddice il fatto che il problema dello zaino èsia [[NP-completo]], dato che <math>W</math>, al contrario di <math>N</math>, non è polinomiale rispetto alla lunghezza dell'input del problema. TaleQuesta lunghezza è proporzionale al numero di bit in <math>W</math>, e non a <math>W</math> stesso.
== Soluzione problema dello zaino 0-1==
ComeSi sopra, indichiamoindichino con <math>w_i</math> il peso dell'i-esimo oggetto e con <math>c_i</math> il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito <math>W</math>. Definiamo <math>A(i,j)</math> come il massimo valore che può essere trasportato con uno zaino di capacità <math>j \le W</math> avendo a disposizione solo i primi <math>i</math> oggetti.
Si può definire <math>A(i,j)</math> ricorsivamente come segue:
* <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>
La soluzioneSi può esseretrovare allorala trovatasoluzione calcolando <math>A(n,W)</math>. Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a <math>O(nW)</math> e uno spazio anch'esso proporzionale a <math>O(nW)</math>, anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a <math>O(W)</math>.
== Algoritmo Greedy ==
Martello e Toth (1990) hanno utilizzato un'[[euristica]] [[Algoritmo greedy|greedy]] per risolvere il problema dello zaino. La loro versione ordina gli oggetti in base al loro costo unitario, vale a dire <math>\frac{c_i}{w_i}</math> e li esamina in ordine decrescente. L'oggetto corrente viene inserito se e solo se il suo peso non supera la capacità residua corrente.
È bene far notare come questiQuesti algoritmi siano euristici: essi, quindi, non garantiscono l'ottimalitàdi dellatrovare la soluzione ottima, ma sono in grado di fornire una "buona" soluzione in tempo ragionevole; spesso questo tipo di algoritmi viene utilizzato in approcci di enumerazione implicita come gli algoritmi [[Branch and bound]].
== Rilassamento continuo ==
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.
== Bibliografia ==
| 