Problema dello zaino

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

sia dato uno zaino che possa supportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un'utilità (ovvero un guadagno). Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza eccedere nel peso sostenibile dallo zaino stesso.

Introduzione

Il problema espresso in maniera più formale diventa:

• ognuno degli N oggetti possiede un peso ${\displaystyle w_{i}}$  e un'utilità ${\displaystyle c_{i}}$ ;
• si indica con W il peso massimo sopportabile dallo zaino;
• la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere ${\displaystyle x_{i}}$ ={0,1} con i=1...N

La funzione obiettivo è:

${\displaystyle maxZ=\sum _{i=1}^{N}c_{i}\cdot x_{i}}$ 

I vincoli:

${\displaystyle \sum _{i=1}^{N}w_{i}\cdot x_{i}\leq W}$ 

In base al tipo di variabili ${\displaystyle x_{i}}$  si ha poi la distinzione in:

• problema dello zaino 0-1:

${\displaystyle x_{i}=\left\{0,1\right\}}$  ${\displaystyle \forall i=1,...,N}$ 

ogni oggetto può esserci o non esserci senza ripetizioni;

• problema dello zaino con limiti

${\displaystyle x_{i}\leq b_{i}}$  ${\displaystyle \forall i=1,...,N}$ .

ogni oggetto non può apparire nello zaino più di 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 tale metodo abbia un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema NP-hard, 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, in quanto 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, per molte istanze di comune applicazione, può essere risolto in maniera soddisfacente; 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 ${\displaystyle c_{1},\dots ,c_{n}}$  i guadagni offerti dagli oggetti, e con ${\displaystyle w_{1},\dots ,w_{n}}$  i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo rispettando il vincolo che il peso complessivo sia inferiore al peso massimo consentito ${\displaystyle W}$ . Ora, si indichi con ${\displaystyle A(i)}$  il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore od uguale ad ${\displaystyle i}$ . Ovviamente ${\displaystyle i\leq W}$ , e ${\displaystyle A(W)}$  sarà la soluzione del nostro problema.

Si definiscono gli ${\displaystyle A(i)}$  ricorsivamente come di seguito:

• ${\displaystyle A(0)=0}$ ,
• ${\displaystyle A(i)=\max \lbrace c_{j}+A(i-w_{j})|w_{j}\leq i\rbrace }$ .

Qui si considera zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da ${\displaystyle A(0)}$  fino a ${\displaystyle A(C)}$  si ottiene la soluzione. Dato che il calcolo di ogni ${\displaystyle A(i)}$  implica l'esame di ${\displaystyle n}$  oggetti (che sono tutti stati calcolati in precedenza), e visto che ci sono ${\displaystyle C}$  valori di ${\displaystyle A(i)}$  da calcolare, il tempo impiegato per trovare la soluzione è ${\displaystyle O(nC)}$ .

Ciò non contraddice il fatto che il problema dello zaino è NP-completo, dato che ${\displaystyle C}$ , al contrario di ${\displaystyle n}$ , non è polinomiale rispetto alla lunghezza dell'input del problema. Tale lunghezza è proporzionale al numero di bit in ${\displaystyle C}$ , e non a ${\displaystyle C}$  stesso.

Soluzione problema dello zaino 0-1

Come sopra, si indicano i costi con ${\displaystyle c_{1},\dots ,c_{n}}$  e i corrispondenti valori con ${\displaystyle v_{1},\dots ,v_{n}}$ . Si vuole massimizzare il valore totale soggetto al vincolo che il costo totale deve essere minor di ${\displaystyle C}$ . Si definisce una funzione ricorsiva ${\displaystyle A(i,j)}$  che sia il massimo valore che può essere ottenuto con un costo minore o uguale a ${\displaystyle j}$  utilizzando fino a ${\displaystyle i}$  oggetti.

Si può definire ${\displaystyle A(i,j)}$  in modo ricorsivo come di seguito:

• ${\displaystyle A(0,j)=0}$ ,
• ${\displaystyle A(i,0)=0}$ ,
• ${\displaystyle A(i,j)=A(i-1,j)}$  se ${\displaystyle c_{i}>j}$ ,
• ${\displaystyle A(i,j)=\max \lbrace A(i-1,j),A(i-1,j-c_{i})+v_{i}\rbrace }$  se ${\displaystyle c_{i}\leq j}$ .

La soluzione può essere allora trovata calcolando ${\displaystyle A(n,C)}$ . Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a ${\displaystyle O(nC)}$  e uno spazio anch'esso proporzionale a ${\displaystyle O(nC)}$ , anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a ${\displaystyle O(C)}$ .

Algoritmo Greedy

Martello e Toth (1990) proposero un'euristica greedy per risolvere il problema dello zaino. La loro versione ordina gli oggetti in ordine decrescente di peso per inserirli nello zaino fino all'esaurimento dello spazio disponibile. Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo greedy garantisce che ne siano inseriti nello zaino almeno ${\displaystyle {\frac {k}{2}}}$ .

Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire ${\displaystyle {\frac {c_{i}}{w_{i}}}}$  ed inserirli in ordine decrescente (euristica CUD).

È bene far notare come questi algoritmi siano euristici: essi, quindi, non garantiscono l'ottimalità della soluzione 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 [0, 1] delle variabili ${\displaystyle x_{i}}$  (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 0716710455. A6: MP9, pg.247.

• Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990.

Template:Link AdQ