Dopo aver visto l'algoritmo di Dijkstra utilizzato per trovare il cammino più breve in un grafo pesato, vediamo ora l'algoritmo Knapsack che in riassunto è utilizzato per trovare la combinazione di oggetti che massimizza il valore totale senza superare una capacità massima prestabilita.
Usiamo lo stesso esempio che avevamo usato per l'algoritmo di Dijkstra, il problema dello zaino. In questo caso è un problema di ottimizzazione della combinazione in cui si cerca di selezionare un sottoinsieme di oggetti con il valore massimo considerando un vincolo di capacità massima dello zaino. Quindi il problema consiste nell'individuare l'insieme di oggetti che massimizza il valore totale senza superare la capacità massima dello zaino.
L'algoritmo Knapsack utilizza una sorta di tabella per memorizzare i risultati intermedi dei valori del problema e poi utilizza questi risultati per risolvere il problema completo.
Vediamo un esempio dove ho usato la funzione knapsack() che prende come argomenti la capacità massima dello zaino W, gli array di pesi wt[], valori val[] degli oggetti e il numero totale di oggetti n. La funzione restituisce il valore massimo che può essere ottenuto di oggetti per la capacità dell'ipotetico zaino.
In particolare il programma utilizza una doppia iterazione sui pesi w e sugli oggetti i.
La tabella K di dimensioni (n + 1) x (W + 1) parte con valori 0 e poi continua con i valori intermedi. Per ogni oggetto i si valuta se conviene includere o meno l'oggetto nella selezione. Se il peso wt[i-1] dell'oggetto è minore o uguale al peso corrente w si può considerare l'oggetto come possibile scelta e si sceglie il massimo valore tra l'includere l'oggetto o escluderlo. Se capita il contrario l'oggetto non può essere incluso quindi si mantiene il valore precedente.
Poi la funzione restituisce il valore massimo ottenibile di oggetti.
#include<bits/stdc++.h>
using namespace std;
int knapsack(int W, int wt[], int val[], int n){
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++){
for (w = 0; w <= W; w++){
if (i == 0 || w == 0){
K[i][w] = 0;
}
else if (wt[i - 1] <= w){
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
}
else{
K[i][w] = K[i - 1][w];
}
}
}
return K[n][W];
}
int main(){
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
cout << "Maximum value: " << knapsack(W, wt, val, n) << endl;
return 0;
}
