Ultimo aggiornamento: 2023-04-21
Questa versione del problema dello zaino, pur equivalente a quella che ho originariamente illustrato in laboratorio, è conforme alla notazione utilizzata dal prof. Maniezzo, con l’unica differenza che gli indici dei pesi \(w_i\) e dei valori \(v_i\) iniziano da zero anziché da uno come nello pseudocodice.
Risolviamo il problema dello zaino 0-1 utilizzando la programmazione dinamica. Disponiamo di \(n\) oggetti di pesi interi positivi \(w_0, \ldots, w_{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 \(W\) 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:
W n
w[0] v[0]
...
w[n-1] v[n-1]Per compilare:
gcc -std=c90 -Wall -Wpedantic zaino2.c -o zaino2Per eseguire:
./zaino2 zaino.inQuesto problema si risolve usando la programmazione dinamica. Per farlo, consideriamo la famiglia di problemi \(P(i,q)\), \(i=0, \ldots, n\), \(q=0, \ldots, W\) definiti nel modo seguente:
\(P(i,q)\) consiste nel determinare il sottoinsieme dei primi \(i\) oggetti \(\{0, \ldots, i-1\}\) aventi peso complessivo minore o uguale a \(q\) e valore totale massimo possibile. Se \(i=0\) non ci sono oggetti tra cui scegliere.
La soluzione del nostro problema è \(P(n, W)\).
Sia \(f(i,q)\) la soluzione di \(P(i,q)\); in altre parole, \(f(i,q)\) è il massimo valore ottenibile da un opportuno sottoinsieme di oggetti scelti tra \(\{0, \ldots, i-1\}\) il cui peso totale sia minore o uguale a \(q\).
Sappiamo che \(f(i,0) = 0\) per ogni \(i\) (in un contenitore di capienza zero non possiamo inserire alcun oggetto, per cui il valore totale sarà zero).
Analogamente, se non ci sono oggetti tra cui scegliere la soluzione avrà sempre valore zero, quindi \(f(0, q) = 0\) per ogni \(q\).
Cosa possiamo dire di \(f(i,q)\) nel caso generale? Supponiamo di conoscere le soluzioni di tutti i problemi “più piccoli”, e concentriamoci sull’ultimo oggetto a disposizione, quello di indice \((i-1)\). Abbiamo due possibilità:
Se il peso \(w_{i-1}\) dell’oggetto \((i-1)\) è maggiore della capienza \(q\), allora sicuramente non possiamo inserirlo nello zaino. Di conseguenza il valore ottimo della soluzione \(f(i,q)\) coincide con il valore della soluzione \(f(i-1, q)\), in cui ci limitiamo a scegliere tra gli oggetti \(\{0, 1, \ldots, i-2\}\):
Se il peso \(w_{i-1}\) dell’oggetto \((i-1)\) è minore o uguale alla capienza \(q\), allora potremmo usarlo oppure no.
Se usiamo lo usiamo, il valore massimo ottenibile sarà \(v_{i-1}\) (valore dell’oggetto \(i-1\)) più il valore massimo che possiamo ottenere inserendo un sottoinsieme dei rimanenti oggetti \(\{0, \ldots, i-2\}\) nel contenitore, che a questo punto ha capienza residua \(q - w_{i-1}\). Quindi, se usiamo l’oggetto \((i-1)\), il valore massimo ottenibile è \(f(i-1,q-w_{i-1})+v_{i-1}\).
Se non usiamo l’oggetto \((i-1)\), il valore massimo ottenibile è \(f(i-1,q)\) (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\), \(q=1, \ldots, W\):
\[ f(i,q) = \begin{cases} f(i-1, q) & \mbox{se}\ q < w_{i-1}\\ \max\{f(i-1, q), f(i-1, q-w_{i-1}) + v_{i-1}\} & \mbox{altrimenti} \end{cases} \]