LabASD - Problema dello zaino 0-1

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-23

Risolviamo il problema dello zaino 0-1 utilizzando la programmazione dinamica. Disponiamo di \(n\) oggetti di pesi interi \(p_0, \ldots, p_{n-1}\) e valori reali \(v_0, \ldots, v_{n-1}\). Vogliamo determinare il sottoinsieme di oggetti di peso complessivo minore o uguale a \(C\) il cui valore totale sia massimo possibile.

Il programma legge i dati di input da standard input secondo il seguente formato:

C n
p[0]   v[0]
...
p[n-1] v[n-1]

Suggerimento

Questo problema si risolve usando la programmazione dinamica. Per farlo, consideriamo la famiglia di problemi \(P(i,j)\), \(i=0, \ldots, (n-1)\), \(j=0, \ldots, C\) definiti nel modo seguente:

\(P(i,j)\) consiste nel determinare il sottoinsieme degli oggetti scelti tra \(\{0, \ldots, i\}\) aventi peso complessivo minore o uguale a \(j\) e valore totale massimo possibile.

La soluzione del nostro problema è \(P(n-1, C)\).

Sia \(V(i,j)\) la soluzione di \(P(i,j)\); in altre parole, \(V(i,j)\) è il massimo valore ottenibile da un opportuno sottoinsieme di oggetti scelti tra \(\{0, \ldots, i\}\) il cui peso totale sia minore o uguale a \(j\).

Sappiamo che \(V(i,0) = 0\) per ogni \(i\) (in un contenitore di capienza zero non possiamo inserire alcun oggetto, per cui il valore totale sarà zero).

Che cosa possiamo dire di \(V(0,j)\)? Avendo a disposizione solo il primo oggetto, di peso \(p_0\) e valore \(v_0\), l'unica scelta è di usarlo oppure no. Lo possiamo inserire nel contenitore se la capienza \(j\) è maggiore o uguale a \(p_0\), e in tal caso il valore massimo ottenibile è \(v_0\). Possiamo quindi scrivere:

\[ V(0,j) = \begin{cases} 0 & \mbox{se}\ j < p_0\\ v_0 & \mbox{altrimenti} \end{cases} \]

Cosa possiamo dire di \(V(i,j)\) nel caso generale? Supponiamo di conoscere le soluzioni di tutti i problemi "più piccoli", e concentriamoci sull'oggetto \(i\)-esimo. Abbiamo due possibilità:

  1. Se il peso \(p_i\) dell'oggetto \(i\) è maggiore della capienza \(j\), allora sicuramente non possiamo inserirlo nello zaino. Di conseguenza il valore ottimo della soluzione \(V(i,j)\) coincide con il valore della soluzione \(V(i-1, j)\), in cui ci limitiamo a scegliere tra gli oggetti \(\{0, 1, \ldots, i-1\}\):

  2. Se il peso \(p_i\) dell'oggetto \(i\) è minore o uguale alla capienza \(j\), allora potremmo usarlo oppure no.

    1. Se usiamo l'oggetto \(i\), il valore massimo degli oggetti nello zaino sarà uguale a \(v_i\) più il valore massimo che possiamo ottenere inserendo un sottoinsieme dei rimanenti \(i-1\) oggetti nel contenitore, che a questo punto ha capienza residua \(j - p_i\). Quindi, se usiamo l'oggetto \(i\), il valore massimo ottenibile è \(V(i-1,j-p_i)+v_i\).

    2. Se non usiamo l'oggetto \(i\), il valore massimo ottenibile è \(V(i-1,j)\) (come il caso 1 sopra).

Tra le due opzioni 2.a e 2.b scegliamo quella che produce il valore massimo. Otteniamo quindi la seguente relazione generale, che vale per ogni \(i=1, \ldots, (n-1)\), \(j=0, \ldots, C\):

\[ V(i,j) = \begin{cases} V(i-1, j) & \mbox{se}\ j < p_i\\ \max\{V(i-1, j), V(i-1, j-p_i) + v_i\} & \mbox{altrimenti} \end{cases} \]

File