Ultimo aggiornamento: 2024-04-19
Questa versione del problema dello zaino è 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}\). Fra tutti i sottoinsiemi di oggetti di peso complessivo minore o uguale a \(W\), vogliamo determinare il massimo valore 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. 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.
Il problema da risolvere coincide con \(P(n, W)\).
Sia \(f(i, q)\) la soluzione di \(P(i, q)\): \(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 \(i=0\) non ci sono oggetti tra cui scegliere la soluzione avrà sempre valore zero, quindi \(f(0, q) = 0\) per ogni \(q\).
Cosa si può 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\), 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 scegliamo tra i rimanenti 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 l’oggetto \((i-1)\), il valore massimo ottenibile è \(v_{i-1}\) (valore dell’oggetto \(i-1\)) più il valore massimo ottenibile inserendo nello zaino un sottoinsieme dei rimanenti oggetti \(\{0, \ldots, i-2\}\); dato che abbiamo già inserito l’oggetto \((i-1)\), la capienza residua dello zaino è \(q - w_{i-1}\). Quindi, usando 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 massimo valore ottenibile è \(f(i-1, q)\) (come il caso 1 sopra).
Tra le opzioni 2.a e 2.b scegliamo quella che produce il risultato maggiore. 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} \]