Un escursionista ha uno zaino che regge al massimo 10 chili e un mucchio di oggetti utili, ciascuno con un peso e un'utilità. Non può portarli tutti. Quali scegliere per massimizzare l'utilità complessiva senza superare il limite? Il problema dello zaino (in inglese knapsack) sembra un gioco, ma descrive un'infinità di decisioni reali: quali progetti finanziare con un budget fisso, quali file mettere in un supporto di capacità limitata, quali annunci inserire in uno spazio pubblicitario, quali carichi mettere su un camion.
La versione 0/1
Abbiamo n oggetti; l'oggetto i pesa p_i e vale v_i. La capacità è C. Ogni oggetto si prende intero o si lascia: niente frazioni. Si vuole massimizzare la somma dei valori, con la somma dei pesi al massimo C.
Provare tutti i sottoinsiemi richiede 2^n tentativi: con 40 oggetti sono più di mille miliardi. Il problema è NP-difficile in generale, ma quando pesi e capacità sono interi non troppo grandi la programmazione dinamica lo risolve in modo esatto e veloce.
La ricorrenza
Lo stato è una coppia (i, c): il miglior valore ottenibile usando solo i primi i oggetti con capacità c. Per l'oggetto i ci sono due scelte:
- non prenderlo: il valore resta quello di (i − 1, c);
- prenderlo, se p_i ≤ c: il valore è v_i più il migliore ottenibile con i primi i − 1 oggetti e capacità residua c − p_i.
Quindi:
M(i, c) = max( M(i − 1, c), v_i + M(i − 1, c − p_i) )
con M(0, c) = 0 per ogni c.
Un esempio completo
Capacità 7. Oggetti:
| Oggetto | Peso | Valore |
|---|---|---|
| Tenda | 4 | 10 |
| Fornello | 3 | 7 |
| Sacco a pelo | 2 | 6 |
| Torcia | 1 | 2 |
Le combinazioni che rispettano la capacità sono diverse: tenda + fornello (peso 7, valore 17), tenda + sacco a pelo (peso 6, valore 16), fornello + sacco a pelo + torcia (peso 6, valore 15), tenda + sacco a pelo + torcia (peso 7, valore 18). Riempiendo la tabella riga per riga si ottiene, all'ultima riga e colonna 7, proprio il valore 18.
Per sapere quali oggetti formano l'ottimo si ripercorre la tabella all'indietro: torcia presa (capacità residua 6), sacco a pelo preso (residuo 4), fornello non preso, tenda presa (residuo 0). Nota che tenda + fornello, la scelta che riempie lo zaino con i due oggetti più preziosi, vale solo 17.
Questo esempio mostra anche perché la ricostruzione va fatta con cura: si confronta M(i, c) con M(i − 1, c) e, se sono diversi, l'oggetto i è stato preso.
Il codice con memoria ridotta
Ogni riga della tabella dipende solo dalla precedente, quindi basta un array di C + 1 elementi, a patto di scorrere le capacità dalla più grande alla più piccola:
def zaino(pesi, valori, C):
M = [0] * (C + 1)
for p, v in zip(pesi, valori):
for c in range(C, p - 1, -1):
M[c] = max(M[c], v + M[c - p])
return M[C]
Scorrere all'indietro garantisce che M[c − p] si riferisca ancora alla riga precedente, cioè che lo stesso oggetto non venga usato due volte. Scorrendo in avanti si risolverebbe invece lo zaino illimitato, in cui ogni oggetto è disponibile in quantità infinita: un errore che cambia il problema senza dare alcun segnale.
Il costo è proporzionale a n · C. Attenzione: è veloce se C è piccolo, ma C è un numero, non una quantità di dati. Con capacità espresse in grammi invece che in chili la tabella diventa mille volte più grande. Si parla per questo di algoritmo pseudo-polinomiale.
Lo zaino frazionario
Se gli oggetti si possono dividere (sabbia, liquidi, ore di lavoro), il problema diventa facile. Si ordinano gli oggetti per valore per unità di peso decrescente e si riempie lo zaino in quest'ordine, prendendo una frazione dell'ultimo oggetto che non entra intero. Questo approccio avido è ottimo per la versione frazionaria, ma non per quella 0/1: nell'esempio il rapporto più alto è quello del sacco a pelo (3 per chilo), seguito dalla tenda (2,5), dal fornello (circa 2,33) e dalla torcia (2).
Quando la capacità è troppo grande
Se pesi e capacità sono numeri enormi, la tabella non è praticabile. Le alternative:
- PD sui valori: se i valori sono piccoli, si calcola il peso minimo necessario per ottenere ogni valore possibile;
- branch and bound: si usa lo zaino frazionario come limite superiore per potare l'albero delle scelte; su molte istanze reali è molto efficiente;
- schemi di approssimazione: arrotondando i valori a multipli di una certa unità si ottiene una soluzione garantita entro una percentuale scelta dall'ottimo, in tempo polinomiale;
- euristiche avide: veloci e spesso buone, ma senza garanzia.
Varianti comuni
- Zaino multidimensionale: più vincoli contemporaneamente, come peso e volume, o budget e personale.
- Zaino multiplo: più contenitori, come più camion o più dischi.
- Somma di sottoinsiemi: il caso in cui valore e peso coincidono; chiede se si può raggiungere esattamente una certa somma.
In sintesi
- Lo zaino 0/1 sceglie un sottoinsieme di oggetti di valore massimo entro una capacità.
- La programmazione dinamica su (oggetto, capacità) lo risolve in tempo n · C.
- Con un solo array bisogna scorrere le capacità all'indietro, altrimenti si risolve lo zaino illimitato.
- La versione frazionaria si risolve con un ordinamento per valore per unità di peso.
- Per capacità enormi servono branch and bound, approssimazioni o euristiche.
