Suppose we have knapsack whose maximum capacity C is 5 kilograms. We have many expensive items that we want to fit into the knapsack without exceeding the maximum capacity. So, our goal is that the value of the items inside the knapsack is maximum, without exceeding C. Here's a list of the items:
| item #i |
1 |
2 |
3 |
4 |
| weight |
2 |
3 |
4 |
5 |
| benefit |
3 |
4 |
5 |
6 |
The key of this problem lies in 1) determining the space of possible options to fit items inside the knapsack and 2) choose that whose benefit is maximum. For this problem there are three possible actions, determined by the current weight of the knapsack namely:
- if the addition of one i-th item makes the sack weight exceed its capacity (wi > w) then leave then remove the i-th item.
- if
(wi < w), then there are two options from which we have to choose that which provides the sack contents with a maximum benefit
- either remove one item and keep the weight constant
- add the i-th item and check what's the remaining allowed weight and the number of items allowed.
These rules (or actions) are expressed as:
Working the previous rules we arrive at the benefit table B:
| i/W |
0 |
1 |
2 |
3 |
4 |
5 |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
3 |
3 |
3 |
3 |
| 2 |
0 |
0 |
3 |
4 |
4 |
7 |
| 3 |
0 |
0 |
3 |
4 |
5 |
7 |
| 4 |
0 |
0 |
3 |
4 |
5 |
7 |
where B(i,w) is the benefit of having item i that with weight w pounds allowed.
B(0,0) to B(5,0) = 0; because there's space from 0 to 5, but they weight nothing.
B(0,0) to B(0,4) = 0; because there isn't any space into the knapsack
B(1,1) = 0; item 1 weights 2, but the allowed is 1 -> no item, no benefit
B(1,2) = 3; one item allowed (#1), wi = 2, w(allowed) = 2, , wi<w, so bi = 3;
B(1,3) = 3; one item allowed (#1), wi = 2, w(allowed) = 3, wi<w, so bi=3;
...
B(2,2) = 3; two items allowed (1&2), wi = 2,3; w(allowed) = 2, so w1 fits, therefore bi = b1 = 3;
B(2,3) = 4; two items allowed (any from 1 to 3), wi = 2,3; w(allowed) = 4, so w2 fits, therefore bi = b4 = 4;
...
B(2,5) = 7; two items allowed (any from 1 to 5); options are:
- same weight but with one less item -> B(i-1,w) = B(1,5) = 3
- compute remaining weight (w-wi) and try to fit any more items (i-1) -> bi + B(i-1,w-wi) = 4 + B(1,5-3=2) = 4 + 3 = 7
- so what's better is the option #2 because it maximizes the Benefit in the knapsack.
There is another version for the recursion equation:
See the (definitely not shortest but-still-works) code below:
Matlab Code:
item = [1 2 3 4];
wis = [2 3 4 5];
bis = [3 4 5 6];
B = zeros(length(item),Cap);
for i = 1 : length(item)
bi = bis(i); wi = wis(i);
for wk = 1 : Cap % weight allowed in knapsack
if i == 1 && wi > wk
term1 = 0; term2 = 0; term3 = 0;
B(i,wk) = 0;
elseif i == 1 && wi == wk
term1 = 0;
term2 = bi;
term3 = 0;
B(i,wk) = max(term1,term2 + term3);
elseif i == 1 && wk > wi
term1 = 0;
term2 = bi;
term3 = B(i,wk-wi);
B(i,wk) = max(term1,term2 + term3);
elseif i > 1 && wk == wi
term1 = B(i-1,wk);
term2 = bi;
term3 = 0;
B(i,wk) = max(term1,term2 + term3);
elseif i > 1 && wk > wi
term1 = B(i-1,wk);
term2 = bi;
term3 = B(i,wk-wi);
B(i,wk) = max(term1,term2 + term3);
elseif i > 1 && wi > wk
term1 = B(i-1,wk);
term2 = 0;
term3 = 0;
B(i,wk) = max(term1,term2 + term3);
end
end
end
Resources
The knapsack problem manifests itself in many practical situations. Here's a list of some of them (click) and also here's a technical book (which I haven't read) with many algorithms (click) and another FREE! book (here). There's also a nice explanation
here.
I checked out the book from my university library to learn a little bit about dynamic programming. The book is very attractive because it's very concise (156 pages). For me the main merit of the book consists in introducing the reader to some of the most common problems tackled with dynamic programming. The main drawback is the notation, which is not straightforward.
