Problema dello zaino

Da Wikipedia, l'enciclopedia libera.
In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie

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

sia dato uno zaino che possa sopportare un determinato peso. Siano dati inoltre N 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[modifica | modifica wikitesto]

Il problema espresso in maniera più formale diventa:

  • ognuno degli N oggetti possiede un peso w_i e un valore 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 x_i.

La funzione obiettivo è:

\max Z = \sum_{i=1}^N c_i\cdot x_i

I vincoli:

\sum_{i=1}^N w_i\cdot x_i\leq W

In base al tipo di variabili x_i si ha poi la distinzione in:

  • problema dello zaino 0-1:
x_i=\left\{0,1\right\} \quad \forall i=1,...,N
ogni oggetto può esserci o non esserci senza ripetizioni;
  • problema dello zaino con limiti
x_i \leq b_i \quad \forall i=1,...,N
ogni oggetto non può apparire nello zaino più di un certo numero di volte;
  • problema dello zaino senza limiti
x_i \in \N \quad \forall i=1,...,N
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-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, 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[modifica | modifica wikitesto]

Viene descritta di seguito la soluzione per il problema dello zaino senza limiti.

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

Si definiscono gli A(k) ricorsivamente come di seguito:

  • A(0) = 0,
  • A(k)=\max \lbrace c_j + A(k - w_j) | w_j \le k \rbrace .

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

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

Soluzione problema dello zaino 0-1[modifica | modifica wikitesto]

Come sopra, indichiamo con w_i il peso dell'i-esimo oggetto e con c_i il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito W. Definiamo A(i,j) come il massimo valore che può essere trasportato con uno zaino di capacità j \le W avendo a disposizione solo i primi i oggetti.

Si può definire A(i,j) ricorsivamente come segue:

  • A(0, j) = 0,
  • A(i, 0) = 0,
  • A(i,j) = A(i - 1, j) se w_i > j,
  • A(i,j) = \max \lbrace A(i - 1, j),  A(i - 1, j - w_i) + c_i \rbrace se w_i\le j.

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

Algoritmo Greedy[modifica | modifica wikitesto]

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 \frac{c_i}{w_i} 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 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[modifica | modifica wikitesto]

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in [0, 1] delle variabili 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[modifica | modifica wikitesto]