Problema dello zaino
Il problema dello zaino consiste nel selezionare un numero k di oggetti all'interno di un insieme di n oggetti per riempire interamente il volume uno zaino.
In termini di ottimizzazione matematica, il problema può essere visto come una combinazione lineare di n elementi w.
$$ x_1 a_1 + x_2 a_2 + ... + x_n a_n = \sum_{i=1}^n x_i a_i = V $$
Gli oggetti sono rappresentati dalle variabili ai mentre la selezione o meno degli oggetti viene fatta con la variabile xi che può assumere il valore 0 (non selezionato) oppure 1 (selezionato). La variabile V indica il volume totale dello zaino.
Questo problema può avere nessuna, una o più soluzioni.
Il problema dello zaino è considerato NP-completo nella sua formulazione generale. Questo significa che non è noto un algoritmo che lo risolva in tempo polinomiale per tutti i casi. Tuttavia, esistono metodi di approssimazione e algoritmi pseudo-polinomiali per casi specifici che possono essere efficaci.
Esempio
Per spiegare in cosa consiste il problema dello zaino farò un esempio molto semplice.
Considero cinque numeri:
$$ 2, 7, 8, 11, 12 $$
Devo trovare i coefficienti xi per fare in modo che la somma dei numeri sia uguale a 21.
$$ x_1 \cdot 2 + x_2 \cdot 7 + x_3 \cdot 8 + x_4 \cdot 11 + x_5 \cdot 12 = 21 $$
Dove x1, x2, ..., x5 possono assumere i valori interi 0 oppure 1.
Per trovare la combinazione dovrei analizzare tutte le combinazioni possibili dei pesi.
In questo caso ci sono 25 = 32 combinazioni da analizzare.
Alla fine il problema ha due soluzioni x=[1 0 1 1 0] e x=[1 1 0 0 1].
- Soluzione 1
Il vettore x=[1 0 1 1 0] indica che le variabili x hanno questi valori x1=1, x2=0, x3=1, x4=1, x5=0. $$ 1 \cdot 2 + 0 \cdot 7 + 1 \cdot 8 + 1 \cdot 11 + 0 \cdot 12 = 2+8+11 = 21 $$ - Soluzione 2
Il vettore x=[1 1 0 0 1] invece indica che le variabili x hanno questi valori x1=1, x2=1, x3=0, x4=1, x5=1. $$ 1 \cdot 2 + 1 \cdot 7 + 0 \cdot 8 + 0 \cdot 11 + 1 \cdot 12 = 2+7+12 = 21 $$
In entrambi i casi il risultato è 21.
Questo problema è molto semplice da risolvere perché le combinazioni possibili sono molto poche (32 combinazioni). Quindi, posso risolverlo per enumerazione.
La difficoltà del problema cresce con il numero degli elementi da considerare.
Le combinazioni 2n crescono in modo esponenziale con il numero degli oggetti da considerare. Quindi, in generale il problema dello zaino è un problema di difficile soluzione.
Il caso delle successioni supercrescenti
Il problema dello zaino può essere risolto in un tempo polinomiale se gli elementi dell'insieme formano una successione supercrescente.
Una successione è supercrescente se ogni termine è maggiore della somma dei termini precedenti. Ad esempio, la successione 1, 3, 7, 15, 27 è supercrescente perché $$ 3>1 \\ 7>1+3 \\ 15> 1+3+7 \\ 27 >1+3+7+15 $$
In questi casi il problema diventa del tipo P (problema polinomiale) e posso risolverlo usando questo algoritmo:
- Ordino i numeri in modo crescente. Dove an è il termine più grande. $$ a_1, a_2, ... , a_n $$
- Confronto l'ultimo termine an della successione con il totale che "m" devo riempire (lo spazio nello zaino). Se lo spazio (m) può contenerlo, gli assegno un peso xn=1 e riduco lo spazio residuo disponibile m=m-an. In caso contrario, gli assegno un peso nullo xn=0. $$ x_n = \begin{cases} 1 \ \ se \ m \ge a_n \\ \\ 0 \ \ se \ m < a_n \end{cases} $$
- Proseguo a ritroso con il termine precedente della successione xn-1 e lo confronto con lo spazio residuo "m" nello zaino. Se lo spazio residuo (m) può contenerlo, gli assegno un peso xn-1=1 e riduco lo spazio residuo disponibile m=m-an-1. In caso contrario, gli assegno un peso nullo xn-1=0. $$ x_i = \begin{cases} 1 \ \ se \ m - \sum_{k=i+1}^n x_k \cdot a_k \ge a_n \\ \\ 0 \ \ se \ m - \sum_{k=i+1}^n x_k \cdot a_k < a_n \end{cases} $$
- L'algoritmo continua a iterare proseguendo sui termini precedenti fino quando lo spazio residuo si annulla (m=0) o non ci sono più termini della successione da valutare.
- Se lo spazio si annulla (m=0) vengono posti a zero tutti i pesi non assegnati e l'algoritmo termina l'esecuzione perché ha trovato una soluzione del problema.
- Se non ci sono più termini della successione da valutare, l'algoritmo termina senza aver trovato una soluzione al problema.
Esempio. Considero l'insieme A e uno "zaino" che ha un volume m=18.
$$ A = \{ 15, 1, 7, 27, 3 \} $$
Devo trovare quali elementi "entrano" nel mio zaino occupando completamente ogni spazio libero.
In altre parole devo trovare i pesi x di questa combinazione lineare.
$$ x_1 a_1 + x_2 a_2 + ... + x_n a_n = \sum_{i=1}^n x_i a_i = 18 $$
Dove le variabili "x" sono i pesi che possono assumere i valori 0 e 1 mentre le variabili "an" sono gli elementi dell'insieme A.
Ordino i termini dell'insieme in modo crescente e verifico se si tratta di una successione supercrescente.
$$ a_n = 1, 3, 7, 15, 27 $$
La combinazione lineare del problema è la seguente:
$$ x_1 \cdot 1 + x_2 \cdot 3 + x_3 \cdot 7 + x_4 \cdot 15 + x_5 \cdot 27 = 18 $$
Dove a1=1, a2=3, a3=7, a4=15, a5=27.
E' una successione supercrescente.
Quindi, posso usare l'algoritmo polinomiale di risoluzione.
- Confronto l'ultimo termine della successione a5=27 con lo spazio da riempire m=18. Poiché m<a5 l'oggetto non può entrare nello zaino. Quindi, gli assegno un peso x5=0. $$ x_1 \cdot 1 + x_2 \cdot 3 + x_3 \cdot 7 + x_4 \cdot 15 + \color{red} 0 \cdot 27 = 18 $$
- Confronto il termine precedente a4=15 con lo spazio da riempire m=18. Poiché m<a4 l'oggetto può entrare nello zaino. Quindi, gli assegno un peso x4=1 e aggiorno lo spazio residuo disponibile nello zaino m=18-15 ovvero m=3. $$ x_1 \cdot 1 + x_2 \cdot 3 + x_3 \cdot 7 + \color{red} 1 \cdot 15 + \color{red} 0 \cdot 27 = 18 $$
- Confronto il termine precedente a3=7 con lo spazio residuo da riempire m=3. Poiché m<a3 l'oggetto non può entrare nello zaino. Quindi, gli assegno un peso x3=0. $$ x_1 \cdot 1 + x_2 \cdot 3 + \color{red} 0 \cdot 7 + \color{red} 1 \cdot 15 + \color{red} 0 \cdot 27 = 18 $$
- Confronto il termine precedente a2=3 con lo spazio residuo da riempire m=3. Poiché m≥a2 l'oggetto può entrare nello zaino. Quindi, gli assegno un peso x2=1 e aggiorno lo spazio residuo disponibile nello zaino m=3-3 ovvero m=0. $$ x_1 \cdot 1 + \color{red} 1 \cdot 3 + \color{red} 0 \cdot 7 + \color{red} 1 \cdot 15 + \color{red} 0 \cdot 27 = 18 $$
- Lo spazio residuo nello zaino è zero (m=0). L'algoritmo assegna pesi nulli ai restanti termini della soluzione. In questo caso solo x1=0 e restituisce la soluzione. $$ \color{red} 0 \cdot 1 + \color{red} 1 \cdot 3 + \color{red} 0 \cdot 7 + \color{red} 1 \cdot 15 + \color{red} 0 \cdot 27 = 18 $$
Pertanto, la soluzione del problema è 3+15=18.
$$ 3 + 15 = 18 $$
Questi due elementi entrano nello zaino occupando tutto lo spazio disponibile (18).
Nota. Questo algoritmo trova una sola soluzione del problema. La prima che trova. In generale il problema dello zaino potrebbe avere anche più soluzioni. Tuttavia, se l'algoritmo non trova nessuna soluzione, è sicuro che non ci sono soluzioni al problema. Ovviamente questo algoritmo funziona solo se la successione è supercrescente. Quindi, in generale il problema dello zaino resta un problema NP completo ovvero molto difficile da risolvere.
E così via.
