Problema dello zaino

Il problema dello zaino, o in inglese Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente^[1].

Sia dato uno zaino che possa sopportare un determinato peso e siano dati

N

oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

Il problema rappresenta un classico esempio di programmazione dinamica e illustra perfettamente il concetto di sottostruttura ottimale, dove la soluzione ottimale del problema può essere costruita combinando soluzioni ottime dei sottoproblemi^[2].

Introduzione

Il problema espresso in maniera più formale diventa:

ognuno degli $N$ oggetti possiede un peso $w_{i}$ e un valore $c_{i}$ ;
si indica con $W$ il peso massimo sopportabile dallo zaino;
la possibilità che un oggetto venga inserito o meno nello zaino è espressa dalle variabili intere $x_{i}$ .

La funzione obiettivo da massimizzare è:

Z=\sum _{i=1}^{N}c_{i}\cdot x_{i}.

I vincoli:

\sum _{i=1}^{N}w_{i}\cdot x_{i}\leq W.

In base al tipo di variabili $x_{i}$ si ha poi la distinzione in:

problema dello zaino 0-1

x_{i}=\left\{0,1\right\}\quad \forall i=1,\ldots ,N,

ogni oggetto può esserci o non esserci senza ripetizioni (abbiamo un solo esemplare di ciascun oggetto);

problema dello zaino con limiti

x_{i}\leq b_{i}\quad \forall i=1,\ldots ,N,

ogni oggetto può apparire nello zaino al massimo

b_{i}

volte (abbiamo

b_{1}

esemplari dell'oggetto 1,

b_{2}

esemplari dell'oggetto 2 e così via);

problema dello zaino senza limiti

x_{i}\in \mathbb {N} \quad \forall i=1,\ldots ,N,

ogni oggetto può apparire nello zaino un numero arbitrario di volte.

Complessità computazionale

Il problema dello zaino è risolto spesso usando la programmazione dinamica, anche se è noto che questo metodo ha un tempo di risoluzione non lineare per questo genere di problema. Il problema generale dello zaino è un problema NP-difficile e questo ha indirizzato la ricerca verso il problema Subset-sum come base per il sistema di crittografia a chiave pubblica, come Merkle-Hellman^[3]. Questi tentativi usavano tipicamente alcuni gruppi oltre agli interi. Merkle-Hellman e altri algoritmi simili vennero presto abbandonati poiché i sottoproblemi di somma che producevano erano risolvibili da algoritmi lineari.

La versione decisionale di questo problema è NP-completa e infatti è uno dei 21 problemi NP-completi di Karp.

Il problema dello zaino, nella versione di ottimizzazione, è di fondamentale importanza in quanto può essere risolto in maniera soddisfacente in molti casi di comune applicazione; infatti per questo problema sono disponibili buone euristiche e buoni rilassamenti. Un algoritmo di enumerazione implicita, ad esempio Branch and bound, normalmente non impiega molto tempo per risolverlo.

Analisi della complessità

Variante	Complessità temporale	Complessità spaziale	Note
Zaino 0-1 (DP)	O(nW)	O(nW) o O(W)	Pseudo-polinomiale
Zaino senza limiti (DP)	O(nW)	O(W)	Pseudo-polinomiale
Zaino frazionario (Greedy)	O(n log n)	O(1)	Polinomiale
Branch and Bound	O(2ⁿ)	O(n)	Esponenziale (caso peggiore)

La complessità O(nW) è pseudo-polinomiale perché dipende dal valore numerico W, non dalla sua lunghezza in bit (log W)^[4].

Soluzione problema dello zaino senza limiti

Viene descritta di seguito la soluzione per il problema dello zaino senza limiti.

Si indichino con $c_{1},\ldots ,c_{N}$ i guadagni offerti dagli oggetti, e con $w_{1},\ldots ,w_{N}$ i pesi di ogni oggetto. Si desidera massimizzare il guadagno complessivo mantenendo il peso complessivo minore o uguale al peso massimo consentito $W$ (vincolo). Si indichi con $A(k)$ il valore massimo di guadagno che si può ottenere rispettando il vincolo che il peso complessivo sia minore o uguale a $k$ . Ovviamente $k\leq W$ e $A(W)$ è la soluzione del problema.

Si definiscono gli $A(k)$ ricorsivamente come di seguito:

$A(0)=0;$
$A(k)=\max \lbrace c_{j}+A(k-w_{j})|w_{j}\leq k\rbrace .$

avendo considerato zero il massimo dell'insieme vuoto. Se si tabulano i risultati a partire da $A(0)$ fino a $A(W)$ si ottiene la soluzione. Dato che il calcolo di ogni $A(k)$ implica l'esame di $N$ oggetti, tutti calcolati in precedenza, e visto che ci sono $W$ valori di $A(k)$ da calcolare, il tempo impiegato per trovare la soluzione è $O(NW)$ .

Ciò non contraddice il fatto che il problema dello zaino sia NP-completo, dato che $W$ , al contrario di $N$ , non è polinomiale rispetto alla lunghezza dell'input del problema. Questa lunghezza è proporzionale al numero di bit in $W$ , e non a $W$ stesso.

Implementazione zaino senza limiti

KNAPSACK_UNLIMITED(pesi, valori, n, W):
    // Inizializzazione
    dp[0] = 0
    for w = 1 to W:
        dp[w] = 0
    
    // Riempimento tabella DP
    for w = 1 to W:
        for i = 1 to n:
            if pesi[i] <= w:
                dp[w] = max(dp[w], dp[w - pesi[i]] + valori[i])
    
    return dp[W]

Soluzione problema dello zaino 0-1

Si indichino con $w_{i}$ il peso dell'i-esimo oggetto e con $c_{i}$ il suo valore. Si vuole massimizzare il valore totale rispettando il vincolo che il peso totale sia minore o uguale al peso massimo consentito $W$ . Definiamo $A(i,j)$ come il massimo valore che può essere trasportato con uno zaino di capacità $j\leq W$ avendo a disposizione solo i primi $i$ oggetti.

Si può definire $A(i,j)$ ricorsivamente come segue:

$A(0,j)=0,$
$A(i,0)=0,$
$A(i,j)=A(i-1,j)$ se $w_{i}>j,$
$A(i,j)=\max \lbrace A(i-1,j),A(i-1,j-w_{i})+c_{i}\rbrace$ se $w_{i}\leq j.$

Si può trovare la soluzione calcolando $A(n,W)$ . Per farlo in modo efficiente si può usare una tabella che memorizzi i calcoli fatti precedentemente. Questa soluzione impiegherà quindi un tempo proporzionale a $O(nW)$ e uno spazio anch'esso proporzionale a $O(nW)$ , anche se con alcune piccole modifiche si può ridurre lo spazio utilizzato a $O(W)$ .

Implementazione dettagliata zaino 0-1

Versione con tabella completa

KNAPSACK_01_FULL(pesi, valori, n, W):
    // Creazione tabella DP
    dp = array[n+1][W+1]
    
    // Inizializzazione casi base
    for i = 0 to n:
        dp[i][0] = 0
    for w = 0 to W:
        dp[0][w] = 0
    
    // Riempimento tabella
    for i = 1 to n:
        for w = 1 to W:
            // Non includiamo l'oggetto i
            dp[i][w] = dp[i-1][w]
            
            // Includiamo l'oggetto i se possibile
            if pesi[i] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w-pesi[i]] + valori[i])
    
    return dp[n][W]

Versione ottimizzata per spazio

KNAPSACK_01_OPTIMIZED(pesi, valori, n, W):
    // Array monodimensionale
    dp = array[W+1]
    
    // Inizializzazione
    for w = 0 to W:
        dp[w] = 0
    
    // Processa ogni oggetto
    for i = 1 to n:
        // Scorri da destra a sinistra per evitare conflitti
        for w = W down to pesi[i]:
            dp[w] = max(dp[w], dp[w - pesi[i]] + valori[i])
    
    return dp[W]

Ricostruzione della soluzione

Per ricostruire quali oggetti fanno parte della soluzione ottimale:

RECONSTRUCT_SOLUTION(dp, pesi, valori, n, W):
    soluzione = []
    i = n
    w = W
    
    while i > 0 and w > 0:
        // Se il valore deriva dall'inclusione dell'oggetto i
        if dp[i][w] != dp[i-1][w]:
            soluzione.append(i)
            w = w - pesi[i]
        i = i - 1
    
    return reverse(soluzione)

Esempio passo-passo

Consideriamo 3 oggetti con zaino di capacità 5:

Oggetto 1: peso=2, valore=1
Oggetto 2: peso=3, valore=4
Oggetto 3: peso=4, valore=7

Tabella DP:

i\w	2	3	4	5
0	0	0	0	0
1	1	1	1	1
2	1	4	4	5
3	1	4	7	7

Soluzione ottimale: Valore = 7 (solo oggetto 3)

Algoritmo Greedy

Martello e Toth (1990) hanno utilizzato un'euristica greedy per risolvere il problema dello zaino^[5]. La loro versione ordina gli oggetti in base al loro costo unitario, vale a dire ${\frac {c_{i}}{w_{i}}}$ e li esamina in ordine decrescente. L'oggetto corrente viene inserito se e solo se il suo peso non supera la capacità residua corrente.

Implementazione algoritmo greedy

KNAPSACK_GREEDY(pesi, valori, n, W):
    // Calcola rapporto valore/peso
    rapporti = []
    for i = 1 to n:
        rapporti[i] = valori[i] / pesi[i]
    
    // Ordina per rapporto decrescente
    oggetti_ordinati = sort_by_ratio_desc(rapporti)
    
    // Algoritmo greedy
    peso_corrente = 0
    valore_totale = 0
    soluzione = []
    
    for oggetto in oggetti_ordinati:
        if peso_corrente + pesi[oggetto] <= W:
            soluzione.append(oggetto)
            peso_corrente += pesi[oggetto]
            valore_totale += valori[oggetto]
    
    return valore_totale, soluzione

Questi algoritmi sono euristici, quindi non garantiscono di trovare la soluzione ottima, ma sono in grado di fornire una "buona" soluzione in tempo ragionevole; spesso questo tipo di algoritmi viene utilizzato in approcci di enumerazione implicita come gli algoritmi Branch and bound.

Analisi del rapporto di approssimazione

Per il problema dello zaino 0-1, l'algoritmo greedy non garantisce alcun rapporto di approssimazione costante. Tuttavia, per il problema dello zaino frazionario (dove si possono prendere frazioni di oggetti), l'algoritmo greedy è ottimale^[6].

Rilassamento continuo

Si dimostra che il rilassamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in $[0,1]$ delle variabili $x_{i}$ , in particolare una sola variabile avrà valore non binario. In questo modo euristica e rilassamento possono essere risolti simultaneamente in maniera efficiente.

Soluzione del rilassamento

KNAPSACK_FRACTIONAL(pesi, valori, n, W):
    // Ordina per rapporto valore/peso decrescente
    oggetti = sort_by_value_weight_ratio_desc(pesi, valori)
    
    peso_corrente = 0
    valore_totale = 0
    soluzione = array[n] // frazione di ogni oggetto
    
    for i = 1 to n:
        if peso_corrente + pesi[oggetti[i]] <= W:
            // Prendi tutto l'oggetto
            soluzione[oggetti[i]] = 1
            peso_corrente += pesi[oggetti[i]]
            valore_totale += valori[oggetti[i]]
        else:
            // Prendi frazione dell'oggetto
            frazione = (W - peso_corrente) / pesi[oggetti[i]]
            soluzione[oggetti[i]] = frazione
            valore_totale += frazione * valori[oggetti[i]]
            break
    
    return valore_totale, soluzione

Algoritmi di approssimazione

Algoritmo 2-approssimato

Un semplice algoritmo 2-approssimato per il problema dello zaino 0-1:

KNAPSACK_2_APPROX(pesi, valori, n, W):
    // Soluzione 1: algoritmo greedy
    valore_greedy, sol_greedy = KNAPSACK_GREEDY(pesi, valori, n, W)
    
    // Soluzione 2: oggetto di valore massimo
    valore_max = 0
    oggetto_max = 0
    for i = 1 to n:
        if pesi[i] <= W and valori[i] > valore_max:
            valore_max = valori[i]
            oggetto_max = i
    
    // Restituisci la migliore delle due
    if valore_greedy >= valore_max:
        return valore_greedy, sol_greedy
    else:
        return valore_max, [oggetto_max]

FPTAS (Fully Polynomial-Time Approximation Scheme)

Esiste un FPTAS per il problema dello zaino che garantisce una soluzione (1+ε)-approssimata in tempo O(n³/ε)^[7]:

KNAPSACK_FPTAS(pesi, valori, n, W, epsilon):
    // Scala i valori per ridurre la complessità
    V_max = max(valori)
    K = epsilon * V_max / n
    
    valori_scalati = []
    for i = 1 to n:
        valori_scalati[i] = floor(valori[i] / K)
    
    // Risolvi con DP sui valori scalati
    return KNAPSACK_BY_VALUE(pesi, valori_scalati, n, W, K)

Varianti avanzate

Problema dello zaino multidimensionale

Estensione con più vincoli di peso:

// Zaino con m dimensioni (es: peso, volume, costo)
MULTIDIMENSIONAL_KNAPSACK(pesi, valori, n, capacita, m):
    // DP con m+1 dimensioni
    dp = array[n+1][capacita[1]+1]...[capacita[m]+1]
    
    // Inizializzazione
    // ... (tutti gli elementi a 0)
    
    for i = 1 to n:
        for c1 = capacita[1] down to pesi[i][1]:
            for c2 = capacita[2] down to pesi[i][2]:
                // ... per tutte le m dimensioni
                for cm = capacita[m] down to pesi[i][m]:
                    dp[c1][c2]...[cm] = max(
                        dp[c1][c2]...[cm],
                        dp[c1-pesi[i][1]][c2-pesi[i][2]]...[cm-pesi[i][m]] + valori[i]
                    )
    
    return dp[capacita[1]][capacita[2]]...[capacita[m]]

Problema dello zaino con conflitti

Alcuni oggetti non possono essere selezionati insieme:

KNAPSACK_WITH_CONFLICTS(pesi, valori, n, W, conflitti):
    // Usa branch and bound o programmazione intera
    // conflitti[i][j] = true se oggetti i e j sono in conflitto
    
    function is_valid(soluzione):
        for i in soluzione:
            for j in soluzione:
                if i != j and conflitti[i][j]:
                    return false
        return true
    
    // Algoritmo di backtracking
    return BACKTRACK_KNAPSACK(pesi, valori, W, conflitti, [], 0)

Applicazioni pratiche

Allocazione risorse

Budget allocation: Distribuzione ottimale di fondi tra progetti
Portfolio optimization: Selezione di investimenti con budget limitato
Resource scheduling: Assegnazione di risorse computazionali

Informatica

Memory management: Ottimizzazione dell'uso della memoria cache
Bandwidth allocation: Distribuzione della banda di rete
Load balancing: Distribuzione del carico sui server

Logistica

Cargo loading: Caricamento ottimale di container e aerei
Cutting stock: Minimizzazione dello spreco in taglio di materiali
Bin packing: Ottimizzazione dello spazio in magazzini

Crittografia

Subset-sum cryptography: Base per sistemi crittografici (ormai obsoleti)
Lattice-based cryptography: Varianti moderne per crittografia post-quantistica

Strumenti e librerie

Implementazioni efficienti

Per problemi reali di grandi dimensioni, sono disponibili solver specializzati:

CPLEX: Solver commerciale per programmazione lineare intera
Gurobi: Solver avanzato con supporto per problemi di zaino
SCIP: Solver open-source per programmazione intera
OR-Tools: Libreria Google per ottimizzazione combinatoria

Note

^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, p. 394-399, ISBN 978-0-262-04630-5.
^ Jon Kleinberg e Éva Tardos, Algorithm Design, Pearson, 2013, p. 260-267, ISBN 978-0321295354.
^ Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, p. 247-248, ISBN 0-7167-1045-5.
^ Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani, Algorithms, McGraw-Hill, 2008, p. 175-178, ISBN 978-0073523408.
^ Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN 0-471-92420-2.
^ Vijay V. Vazirani, Approximation Algorithms, Springer, 2001, p. 74-77, ISBN 978-3540653677.
^ David P. Williamson e David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, p. 65-69, ISBN 978-0521195270.

Bibliografia

Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN 0-471-92420-2.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, ISBN 978-0-262-04630-5.
Jon Kleinberg e Éva Tardos, Algorithm Design, Pearson, 2013, ISBN 978-0321295354.
Vijay V. Vazirani, Approximation Algorithms, Springer, 2001, ISBN 978-3540653677.
David P. Williamson e David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, ISBN 978-0521195270.

Voci correlate

Collegamenti esterni

(EN) Eric W. Weisstein, Knapsack Problem, su MathWorld, Wolfram Research.
(EN) Denis Howe, knapsack problem, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
(EN) Stanford CS161: Knapsack Problem
(EN) CP-Algorithms: Knapsack Problem

Portale Informatica

Portale Matematica

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, p. 394-399, ISBN 978-0-262-04630-5.

[2] Jon Kleinberg e Éva Tardos, Algorithm Design, Pearson, 2013, p. 260-267, ISBN 978-0321295354.

[3] Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, p. 247-248, ISBN 0-7167-1045-5.

[4] Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani, Algorithms, McGraw-Hill, 2008, p. 175-178, ISBN 978-0073523408.

[5] Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990, ISBN 0-471-92420-2.

[6] Vijay V. Vazirani, Approximation Algorithms, Springer, 2001, p. 74-77, ISBN 978-3540653677.

[7] David P. Williamson e David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, p. 65-69, ISBN 978-0521195270.

[1]

[2]

[3]

[4]

[5]

[6]

[7]