Ultimo aggiornamento: 2023-04-21
Questa è la versione originariamente proposta in laboratorio durante l’esercitazione di giovedì 20 aprile 2023 (classe B). Qui si usa una notazione leggermente diversa da quella utilizzata a lezione dal prof. Maniezzo, e inoltre i sottoproblemi e il caso base sono definiti in modo leggermente diverso. Per evitare confusione ho realizzato una nuova versione che è maggiormente conforme a quanto fatto dal prof. Maniezzo, sia per la notazione che per la struttura del problema. Per il resto, le due versioni sono del tutto equivalenti.
Risolviamo il problema dello zaino 0-1 utilizzando la programmazione dinamica. Disponiamo di \(n\) oggetti di pesi interi positivi \(p_0, \ldots, p_{n-1}\) e valori reali non negativi \(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 un file il cui nome va specificato sulla riga di comando. Il contenuto del file ha la seguente struttura:
C n
p[0] v[0]
...
p[n-1] v[n-1]Per compilare:
gcc -std=c90 -Wall -Wpedantic zaino.c -o zainoPer eseguire:
./zaino zaino.inQuesto 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} \]
(assumiamo che i valori \(v_i\) siano tutti non negativi).
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à:
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\}\):
Se il peso \(p_i\) dell’oggetto \(i\) è minore o uguale alla capienza \(j\), allora potremmo usarlo oppure no.
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\).
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 che vale per \(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} \]