During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?
For instance, take W = 10 and
Item Weight Value
1 6 $30
2 3 $14
3 4 $16
4 2 $9
Let K(w) = max value achievable with a knapsack of capacity w.
Now if the optimal solution to K(w) includes i, then removing this item from knapsack leaves an optimal solution to K(w-w[i])+v[i], for some i.
As we dont know which i, so we will try all the possibilities.
K(w) = MAX {K(w-w[i] + v[i]} for i:w[i]<w
The maximum over an empty set is 0.
K(0) = 0
for w = 1 to W:
K(w) = max{K(w - wi) + vi: wi <= w}
return K(W)
This algorithm fills in a one-dimensional table of length W + 1, in left-to-right order. Each entry can take up to O(n) time to compute, so the overall running time is O(nW). As always, there is an underlying dag. Try constructing it, and you will be rewarded with a startling insight: this particular variant of knapsack boils down to finding the longest path in a dag!
Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int M = 10;
Code output:
Printing knapsack for different Ws:
0 0 9 14 18 23 30 32 39 44 48
Optimal value for unbounded knapsack: 48
