Problema dello zaino
![Nessuna nota a piè di pagina](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Question_book_magnify.svg/45px-Question_book_magnify.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Knapsack_Problem_Illustration.svg/220px-Knapsack_Problem_Illustration.svg.png)
Il problema dello zaino, o in inglese Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente.
- Sia dato uno zaino che possa sopportare un determinato peso e siano dati 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
Il problema espresso in maniera più formale diventa:
- ognuno degli oggetti possiede un peso e un valore ;
- si indica con il peso massimo sopportabile dallo zaino;
- la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere .
La funzione obiettivo da massimizzare è:
I vincoli:
In base al tipo di variabili si ha poi la distinzione in:
- problema dello zaino 0-1
- ogni oggetto può esserci o non esserci senza ripetizioni (abbiamo un solo esemplare di ciascun oggetto);
- problema dello zaino con limiti
- ogni oggetto può apparire nello zaino al massimo volte (abbiamo esemplari dell'oggetto 1, esemplari dell'oggetto 2 e così via);
- 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 questo metodo ha 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 crittografia a chiave pubblica, come Merkle-Hellman. Questi tentativi usavano tipicamente alcuni gruppi oltre agli interi. Merkle-Hellman e altri algoritmi simili vennero presto abbandonati poiché i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.
La versione decisionale di questo problema è 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 può essere risolto in maniera soddisfacente in molti casi di comune applicazione; infatti per questo problema 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 i guadagni offerti dagli oggetti, e con i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo mantenendo il peso complessivo minore o uguale al peso massimo consentito (vincolo). Si indichi con il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore o uguale a . Ovviamente e è la soluzione del problema.
Si definiscono gli ricorsivamente come di seguito:
avendo considerato zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da fino a si ottiene la soluzione. Dato che il calcolo di ogni implica l'esame di oggetti, tutti calcolati in precedenza, e visto che ci sono valori di da calcolare, il tempo impiegato per trovare la soluzione è .
Ciò non contraddice il fatto che il problema dello zaino sia NP-completo, dato che , al contrario di , non è polinomiale rispetto alla lunghezza dell'input del problema. Questa lunghezza è proporzionale al numero di bit in , e non a stesso.
Soluzione problema dello zaino 0-1
Si indichino con il peso dell'i-esimo oggetto e con il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito . Definiamo come il massimo valore che può essere trasportato con uno zaino di capacità avendo a disposizione solo i primi oggetti.
Si può definire ricorsivamente come segue:
- se
- se
Si può trovare la soluzione calcolando . Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a e uno spazio anch'esso proporzionale a , anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a .
Algoritmo Greedy
Martello e Toth (1990) hanno utilizzato un'euristica greedy per risolvere il problema dello zaino. La loro versione ordina gli oggetti in base al loro costo unitario, vale a dire e li esamina in ordine decrescente. L'oggetto corrente viene inserito se e solo se il suo peso non supera la capacità residua corrente.
Questi algoritmi sono euristici, quindi non garantiscono di trovare 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 delle variabili , in particolare una sola variabile avrà valore non binario. In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.
Bibliografia
- Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
- Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN 0-471-92420-2.
Collegamenti esterni
- (EN) Eric W. Weisstein, Knapsack Problem, su MathWorld, Wolfram Research.
- (EN) Denis Howe, knapsack problem, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)