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.
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.
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