Il problema dello zaino
Il problema dello zaino (o "Knapsack Problem" in inglese) è un problema classico di ottimizzazione combinatoria.
Può essere descritto nel seguente modo:
Dato un insieme di oggetti, ognuno con un proprio peso e un proprio valore, si deve scegliere quali di questi oggetti mettere in uno zaino, in modo che il peso totale non superi la capacità massima dello zaino e il valore totale degli oggetti sia il massimo possibile.
Il problema dello zaino ha molte varianti, ma le due principali sono:
- 0/1 Knapsack Problem
Ogni oggetto può essere scelto al massimo una volta. È chiamato "0/1" perché ogni oggetto può essere rappresentato con una variabile che assume valore 0 se l'oggetto non è incluso nello zaino e 1 se lo è. Questo problema è NP-completo, il che significa che non esiste un algoritmo polinomiale noto che lo risolva per ogni istanza. - Fractional Knapsack Problem
Gli oggetti possono essere frazionati. Questo significa che si può scegliere di prendere solo una parte di un oggetto, piuttosto che l'oggetto intero. Questa variante può essere risolta efficacemente tramite algoritmi greedy.
Le applicazioni del problema dello zaino sono numerose e vanno dalla selezione di investimenti e il caricamento di merci fino alla criptografia.
Esistono diversi approcci per risolvere il problema dello zaino, come l'utilizzo di tecniche di programmazione dinamica per la versione 0/1, o algoritmi greedy per la versione frazionaria. Per le istanze del problema di grande dimensione, possono essere utilizzati anche metodi euristici o metaeuristici, come algoritmi genetici o ricerca tabù, che forniscono soluzioni approssimate in tempi ragionevoli.
Esempio
Facciamo un esempio del problema dello zaino 0/1.
Immaginiamo di avere uno zaino che può portare al massimo 5 kg e i seguenti oggetti da poter scegliere:
- Orologio: peso 1 kg
- Libro: peso 2 kg
- Computer: peso 3 kg
- Ferro da stiro: peso 4 kg
L'obiettivo è utilizzare interamente il carico massimo dello zaino (5 kg).
Dal punto di vista matematico questo problema consiste nel trovare una combinazione lineare:
$$ x_1 w_1 + x_2 w_2 + x_3 w_3 + x_4 w_4 + ... x_n w_n = \sum_{i=1}^n w_i $$
Dove i coefficienti xi possono assumere solo due valori: 0 (fuori lo zaino), 1 (dentro lo zaino).
Le variabile wi indicano invece i pesi degli n oggetti.
$$ x_1 1 \ kg + x_2 \ 2 kg + x_3 \ 3 kg + x_4 4 \ kg = 1 \ kg + 2 \ kg + 3 \ kg + 4 \ kg $$
$$ x_1 1 \ kg + x_2 \ 2 kg + x_3 \ 3 kg + x_4 4 \ kg = 10 \ kg $$
Per trovare la soluzione del problema occorre iterare su ogni oggetto e decidere se includere o meno l'oggetto in questione, entro il limite del carico massimo (5 kg) dello zaino.
| Orologio (1 kg) | Libro (2 kg) | Computer (3 kg) | Ferro da Stiro (4 kg) | Totale | |
|---|---|---|---|---|---|
| 1 | 1 kg | 1 kg | |||
| 2 | 1 kg | 2 kg | 3 kg | ||
| 3 | 1 kg | 2 kg | 3 kg | 6 kg | |
| 4 | 1 kg | 2 kg | 3 kg | 4 kg | 10 kg |
| 5 | 1 kg | 2 kg | 4 kg | 7 kg | |
| 6 | 1 kg | 3 kg | 4 kg | ||
| 7 | 1 kg | 3 kg | 4 kg | 8 kg | |
| 8 | 1 kg | 4 kg | 5 kg | ||
| 9 | |||||
| 10 | 2 kg | 2 kg | |||
| 11 | 2 kg | 3 kg | 5 kg | ||
| 12 | 2 kg | 3 kg | 4 kg | 9 kg | |
| 13 | 2 kg | 4 kg | 6 kg | ||
| 14 | 3 kg | 3 kg | |||
| 15 | 3 kg | 4 kg | 7 kg | ||
| 16 | 4 kg | 4 kg |
In questo caso il problema ha due soluzioni:
- Orologio + ferro da stiro (1 kg + 4 kg)
- Libro + computer (2 kg + 3 kg)
Si tratta di un esempio molto semplice da risolvere perché gli oggetti sono pochi e le combinazioni possibili sono solo 16.
$$ 2^4 = 16 $$
In generale, però, il problema diventa computazionalmente molto difficile da risolvere quando gli oggetti da considerare sono molti, perché il numero delle combinazioni cresce in modo esponenziale $ 2^n $ rispetto al numero degli oggetti.
