Il problema dello zaino

Un'escursionista con un limite di peso, un ladro con un sacco, un'azienda con un budget e una lista di progetti: tutti hanno davanti la stessa domanda. Che cosa conviene mettere dentro per ottenere il valore più alto senza superare il limite? È il problema dello zaino, e la programmazione dinamica lo risolve in modo esatto quando i pesi sono numeri interi non troppo grandi.

Una tabella con gli oggetti sulle righe e le capacità sulle colonne, con il percorso di ricostruzione in arancione, accanto a uno zaino e a oggetti di dimensioni diverse
Una tabella con gli oggetti sulle righe e le capacità sulle colonne, con il percorso di ricostruzione in arancione, accanto a uno zaino e a oggetti di dimensioni diverse

Il problema

Ci sono n oggetti, ognuno con un peso e un valore, e uno zaino che regge al massimo un peso W. Scegli un insieme di oggetti con peso totale al massimo W e valore totale il più alto possibile. Ogni oggetto entra intero o resta fuori, ed è per questo che si chiama problema dello zaino 0/1. Con n oggetti ci sono 2ⁿ insiemi possibili, quindi provarli tutti diventa presto impossibile.

La tabella

Sia best[i][w] il valore massimo che sta nel peso w usando solo i primi i oggetti. Allora best[0][w] = 0, e per ogni riga successiva ci sono due scelte: lasciare fuori l'oggetto i, ottenendo best[i − 1][w], oppure, se il suo peso wᵢ ci sta, metterlo nello zaino, ottenendo il suo valore più best[i − 1][w − wᵢ]. Il maggiore dei due è best[i][w]. Riempiendo la tabella riga per riga, le due celle che servono sono sempre già pronte.

Un esempio

Prendi una capacità di 7 e quattro oggetti con pesi 1, 3, 4 e 5 e valori 1, 4, 5 e 7. Con il solo primo oggetto, ogni capacità da 1 in su vale 1. Aggiungendo il secondo, la capacità 4 può contenerli entrambi per 5. Aggiungendo il terzo, la capacità 7 può contenere gli oggetti 2 e 3 per 9. Il quarto oggetto, di peso 5 e valore 7, potrebbe unirsi all'oggetto 1 per 8 con capacità 6 o 7, ma 9 è meglio, quindi la cella in basso a destra vale 9: si mettono nello zaino gli oggetti di peso 3 e 4.

Quanto è difficile?

La tabella richiede circa n·W passi. Sembra veloce, ma W è un numero, e un numero con d cifre può arrivare a 10 elevato alla d, quindi il lavoro cresce in modo esponenziale con la lunghezza dell'input. Il problema dello zaino è NP-difficile; era uno dei 21 problemi NP-completi di Richard Karp del 1972. In pratica la tabella, il branch and bound e buoni schemi di approssimazione gestiscono bene anche grandi istanze reali.

Storia e applicazioni

Il nome risale al matematico Tobias Dantzig, all'inizio del Novecento, e suo figlio George Dantzig ne diede un classico metodo greedy nel 1957. I problemi dello zaino compaiono nella pianificazione dei budget e nella scelta di portafogli, nel taglio di materie prime con il minor spreco possibile, nel carico delle merci e perfino nei primi sistemi di crittografia a chiave pubblica: il crittosistema di Merkle–Hellman del 1978 si basava su un problema dello zaino e fu violato pochi anni dopo.

George Dantzig (a sinistra) riceve la National Medal of Science dal presidente Gerald Ford nel 1976. Nel 1957 Dantzig diede un classico metodo greedy per il problema dello zaino. Il nome stesso risale a suo padre, Tobias Dantzig.
George Dantzig (a sinistra) riceve la National Medal of Science dal presidente Gerald Ford nel 1976. Nel 1957 Dantzig diede un classico metodo greedy per il problema dello zaino. Il nome stesso risale a suo padre, Tobias Dantzig.

Esploralo

Apri l'app, passa alla vista Tabella e premi Passo. La cella arancione è quella che si sta riempiendo, e le celle blu sono le due che confronta: la cella subito sopra e, nella riga sopra, la cella spostata a sinistra di quanto pesa l'oggetto. Dopo l'ultima cella, la ricostruzione risale in arancione dall'angolo in basso a destra, e gli oggetti nello zaino compaiono sotto la tabella.

Domande frequenti

Qual è la differenza tra zaino 0/1, limitato e illimitato?

Nella versione 0/1 ogni oggetto si prende al massimo una volta. Nella versione limitata ogni oggetto ha un numero limitato di copie, e in quella illimitata un numero qualsiasi. La tabella cambia solo di poco dall'una all'altra.

Il metodo greedy è mai corretto per lo zaino?

Per il problema dello zaino frazionario, in cui gli oggetti si possono dividere, prendere prima il miglior valore per unità di peso è ottimale. Con oggetti interi può sbagliare di molto, anche se la migliore tra la soluzione greedy e il singolo oggetto di maggior valore vale sempre almeno metà del valore migliore.

Quanta memoria serve alla tabella?

(n + 1)·(W + 1) celle per la tabella completa, che è ciò che serve per ricostruire gli oggetti. Se interessa solo il valore migliore, basta una riga di W + 1 celle, riempita da destra a sinistra.

Lo zaino è la stessa cosa della somma di sottoinsiemi?

La somma di sottoinsiemi è il caso particolare in cui il valore di ogni oggetto è uguale al suo peso e la domanda è se lo zaino si può riempire esattamente. Anche questo problema è NP-completo e si risolve con lo stesso tipo di tabella.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova il problema dello zaino