Knapsack
The Knapsack problem is a classic dynamic programming problem. In this problem, we are given a knapsack of size
Unbounded Knapsack
Let’s focus now on the unbounded knapsack problem and let’s start with an example. Suppose we have an unbounded number of tacos, each of weight 2 and value 4. We also have burritos each of weight 6 and value 17. Suppose now that we have a knapsack of size,
A Greedy Approach
The first thought that comes to mind is to try a greedy approach. Perhaps there is some way to pick the items at each step until the knapsack is filled? One simple greedy strategy is to always pick the item with the best value/weight ratio. In the above example, we’ll pick 2 burritos of value
Complete Search
We can also try a complete search of every possible combination of items. We can simulate this by inserting
Dynamic Programming
As we saw above, greedy doesn’t work and exhaustive search takes exponential time. It turns out we can do much better with dynamic programming. To use dynamic programming we need to find an optimal substructure. An optimal substructure means that the solution to the problem will contain within it solutions to smaller subproblems. It turns out we have a beautiful optimal substructure for the Knapsack problem.
Let
In other words, suppose we have unlimited copies of the following
Implementation
typedef struct item {
int w;
int v;
item(int weight, int value) {
w = weight;
v = value;
}
} item;
int unbounded_knapsack(std::vector<item> &bag, int W) {
std::vector<std::vector<int>> items;
std::vector<int> K;
for (int i = 0; i <= W; i++) {
K.push_back(0);
items.push_back(std::vector<int>());
}
// base case, k[0] = 0
for (int w = 1; w <= W; w++) { // for each weight w
for (int i = 0; i < bag.size(); i++) { // for each item i
if (bag[i].w <= w && bag[i].v + K[w - bag[i].w] > K[w]) {
// maybe there is a more effient way?
items[w].clear();
items[w].push_back(i);
items[w].insert(items[w].end(), items[w-bag[i].w].begin(), items[w-bag[i].w].end());
K[w] = bag[i].v + K[w - bag[i].w];
}
}
}
// print items
for (int i = 0; i < items[W].size(); i++) {
printf("(%d %d) ", bag[items[W][i]].w, bag[items[W][i]].v);
}
printf("\n");
printf("Optimal value = %d\n", K[W]);
return K[W];
}
Proof of Correctness
Proof:
Suppose that we have a knapsack of size
We will prove our claim by contradiction. Suppose that
Running Time
Assume we have
0/1 Knapsack
Let’s focus now on the 0/1 knapsack problem and let’s start with an example. Suppose we have a taco of weight 3 and value 10. We also a burrito of weight 6 and value 14 and a enchilada of weight 5 and value 11. Suppose now that we have a knapsack of size,
Complete Search
A greedy approach won’t work similar to the unbounded knapsack. We can instead do an exhaustive search. We can check every possible combination of the items we have. We will have 2 choices for each item. We either select the item or we don’t. Therefore, we have
Dynamic Programming
Unfortunately we can’t use the same recursive substructure in the unbounded knapsack above. In this problem, we need to also keep track of which items are available at each step since some might have been taken. So if the smaller subproblem is using an item
Therefore, our subproblems must track both the size of the knapsack and the items allowed so far and therefore, we need a two dimensional table! we’ll let
Suppose we know the optimal solution to
There are two cases:
Case 1:
Case 2: We do use item
We can therefore, summarize it in:
With the base case of
Proof of Correctness
The proof is very similar to the structure of our earlier proof to the unbounded knapsack problem. If we can have a better solution to the subproblem then we can have even a better solution to the optimal solution to the larger problem which is a contradiction. I might write it later?.
Implementation
int knapsack_01(std::vector<item> &bag, int W) {
int K[100][100] = {0};
// base case k[0][j] = 0, K[i][0] = 0
for (int w = 1; w <= W; w++) { // for each weight w
for (int i = 1; i <= bag.size(); i++) { // for each item i:
// case 1: item i is not in the optimal solution
K[w][i] = K[w][i-1];
// case 2: item i is in the optimal solution
if (bag[i-1].w <= w && bag[i-1].v + K[w - bag[i-1].w][i-1] > K[w][i]) {
K[w][i] = bag[i-1].v + K[w - bag[i-1].w][i-1];
}
}
}
// print items
int res = K[W][bag.size()];
printf("%d\n", res);
int cur_w = W;
int cur_v = K[W][bag.size()];
for (int i = (int)bag.size(); i > 0 && res > 0; i--) {
if (cur_v != K[cur_w][i-1]) {
printf("%d %d\n", bag[i-1].w, bag[i-1].v);
cur_v -= bag[i-1].v;
cur_w -= bag[i-1].w;
}
}
printf("\n");
printf("Optimal value = %d\n", K[W][bag.size()]);
return K[W][bag.size()];
}
Source Code Stanford CS161