Soluzione: Programmazione dinamica
Complessità: $O(Wn)$
Una soluzione efficiente per risolvere il problema è quella che sfrutta la programmazione dinamica attraverso la formula
$V[i, 0]:= 0 \quad\text{ for $1 \le i \le n$.}$
$V[0, j]:= 0 \quad\text{ for $1\le j \le W$.}$
$V[i, j]:= \begin{cases}V[i-1, j], & \text{if $wi[i] > j$.} \\ MAX(V[i-1, j], V[i-1, j - wi[i]] + v[i]) , & \text{if $wi[i] \le j$.} \end{cases}$
con $V[i, j]$ soluzione del sotto-problema che prende in considerazione $i$ oggetti e con zaino che sopporta un peso massimo pari a $j$. Con $wi[i]$ si indica il peso dell'$i$-esimo oggetto dell'insieme e con $v[i]$ il relativo valore. E' facile intuire che
- se $wi[i] > j$, l'oggetto non entrerà nello zaino e quindi $V[i, j] = V[i-1, j]$. Cioè sarà uguale al valore massimo che si aveva senza contare l'$i$-esimo oggetto.
- se $wi[i] \le j$, l'oggetto può entrare nello zaino ma si ha facoltà di inserirlo o meno in modo da avere il massimo tra i due valori possibili in base alla scelta fatta. Quindi $V[i, j] = MAX(V[i-1, j], V[i-1, j - wi[i]] + v[i])$. Cioè sarà uguale al valore massimo che si aveva senza contare l'$i$-esimo oggetto (se si decide di non inserirlo) oppure (se si decide di inserirlo) sarà uguale al valore massimo che si aveva senza contare l'$i$-esimo oggetto quando il peso massimo sopportato dallo zaino era $j - wi[i]$ (il peso sopportato dallo zaino prima di processare l'$i$-esimo oggetto) più il valore dell'$i$-esimo oggetto.
Quello che si ottiene è una matrice che conserva i risultati parziali del problema
Guardando l'immagine sopra risulta più facile notare che il valore impostato nel risultato parziale è quello massimo. Per convincersene basta leggere il codice sorgente e verificare i risultati parziali guardando la suddetta immagine. Come si può notare dal codice sorgente il doppio ciclo for permette di processare la tabella dei risultati parziali riga per riga. Quindi se, ad esempio $i=3$, siamo sulla terza riga (con $w[3]=2$ e $v[3]=7$) e stiamo calcolando $V[3,j]$:
Con $j=1$, $w[3] > j$ e quindi, secondo la formula, $V[3,1]=3$.
Con $j=2$, $w[3]=j$ e quindi, secondo la formula $V[3,2]=Max(V[2,2], V[2,(2-2)]+v[3])=Max(3, (0+7))=7$
Con $j=3$, $w[3]<j$ e quindi, secondo la formula $V[3,3]=Max(V[2,3], V[2,(3-2)]+v[3])=Max(10, (3+7))=10$
Con $j=4$, $w[3]<j$ e quindi, secondo la formula $V[3,4]=Max(V[2,4], V[2,(4-2)]+v[3])=Max(13, (3+7))=13$
E così via.
Inoltre, al fine di tenere traccia degli oggetti inseriti è utile notare che, partendo da $V[n, W]$ e risalendo lungo la colonna, se il valore di $V[n, W]$ è diverso da quello di $V[n-1, W]$ allora l'oggetto $n$-esimo è stato inserito. A quel punto si diminuisce l'indice della riga di 1 e l'indice della colonna di $w[i]$ (per non tener più conto del peso dell'$n$-esimo oggetto) e si ripete la procedura.
Ad esempio, nell'immagine sopra si parte da $V[4, 7] = 30$.
$V[4, 7] \ne V[3, 7]$, che è 20. Quindi il quarto elemento è stato inserito nello zaino. L'elemento ha peso 2, che va sottratto da 7. L'indice della riga passa da 4 a 3 e si va all'iterazione successiva.
$V[3, 5] = 17$, è diverso da $V[2, 5] = 13$. Quindi il terzo elemento è stato inserito nello zaino. L'elemento ha peso 2, che va sottratto da 5. L'indice della riga passa da 3 a 2 e si va all'iterazione successiva.
$V[2, 3] = 10$, è uguale a $V[1, 5]$. Quindi il secondo elemento non è stato inserito nello zaino. L'indice della riga passa da 2 a 1 e si va all'iterazione successiva.
$V[1, 3] = 10$, è diverso da $V[0, 3] = 0$. Quindi il primo elemento è stato inserito nello zaino. L'indice della riga passa da 1 a 0 e si esce dal ciclo.
Prima di passare al codice è utile notare che, per non sprecare spazio negli array che conservano i pesi ed i valori, gli indici vengono scalati di 1 per farli partire da zero. Per questo motivo c'è una piccola differenza tra la formula e la sua implementazione in codice.
/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono una maggiore semplificazione.*/ #include<stdio.h> void pick(unsigned int, unsigned int, unsigned int[], unsigned int[], unsigned int); unsigned int knapSack(unsigned int, unsigned int[], unsigned int[], unsigned int); inline int max(int a, int b) { return (a > b) ? a : b; } int main(int argc, int* argv, char* envp) { unsigned int v[] = { 10, 3, 7, 13 }; unsigned int wi[] = { 3, 1, 2, 2 }; unsigned int W = 7; unsigned int n = sizeof(v) / sizeof(v[0]); printf("Valore degli oggetti presi: %d\n", knapSack(W, wi, v, n)); return 0; } unsigned int knapSack(unsigned int W, unsigned int wi[], unsigned int v[], unsigned int n) { unsigned int i, j, tmp; // Dimensioni di matrice aumentate di 1 perchè peso e oggetto corrente // devono poter raggiungere W ed n, rispettivamente. unsigned int* VP = new unsigned int[(n + 1) * (W + 1)]; // Se il peso sopportato da zaino è zero caso è banale: valore di oggetti presi = 0 for (i = 0; i <= n; i++) VP[i * (W + 1) + 0] = 0; // Se non ci sono oggetti da prendere caso è banale: valore di oggetti presi = 0 for (j = 0; j <= W; j++) VP[0 * (n + 1) + j] = 0; for (i = 1; i <= n; i++) { for (j = 1; j <= W; j++) { // Se il peso dell'i-esimo oggetto è minore del peso supportato dallo zaino // prende o lascia l'oggetto (scelta migliore; // i-1 perchè zero è un indice valido mentre n non lo è per gli array) if (wi[i - 1] <= j) VP[i * (W + 1) + j] = max( (v[i - 1] + VP[(i - 1) * (W + 1) + (j - wi[i - 1])]), VP[(i - 1) * (W + 1) + j] ); else // altrimenti lo lascia VP[i * (W + 1) + j] = VP[(i - 1) * (W + 1) + j]; } } pick(i - 1, j - 1, &VP[0], wi, W + 1); tmp = VP[n * (W + 1) + W]; delete[] VP; return tmp; } void pick(unsigned int i, unsigned int w, unsigned int VP[], unsigned int wi[], unsigned int W) { while (w > 0) { for (; i > 0; --i) { if (VP[i * W + w] != VP[(i - 1) * W + w]) { printf("Oggetto con indice %d selezionato\n", i - 1); w -= wi[(i)-1]; --i; break; } } } }
Riferimenti:
[1] http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
[2] https://bruceoutdoors.wordpress.com/2015/12/14/1-0-knapsack-problem-a-hands-on-guide-c/
Nessun commento:
Posta un commento