The Knapsack problem is a classic dynamic programming problem. In this problem, we are given a knapsack of size $W$ for some integer $W$ and a list of items. Each item $x_i$ has an integer weight $w_i$ and an integer value, $v_i$. The goal is to maximize the value of the knapsack under the constraint $W$. There are many variations of the Knapsack problem. 0/1 Knapsack puts a limit of at most 1 copy of each item that you can pack in the knapsack. So we either select an item $x_i$ or we don’t. There is also the unbounded knaspack where you have multiple/unbounded copies of each item.

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, $W=14$. The optimal solution is to pack 2 burritos and 1 taco which will give an optimal value of $2*17+1*4=38$.

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 $2*17=34$ which is not an optimal value.

Complete Search

We can also try a complete search of every possible combination of items. We can simulate this by inserting $\lceil W/x_i \rceil$ copies of item $x_i$ to a new list of items. If we originally had $n$ items, we could potentially insert $O(n^2)$ items in the new list. We can now iterate through the list and for each item in the list, we can either select the item to be in the knapsack or not. Therefore, the running time will be $O(2^{n^2})$.

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 $K[x]$ be the optimal value for capacity $x$. We will have the following recursive substructure:

$$ \begin{align*} K[x] = \max_i\{K[x - w_i] + v_i\} \end{align*} $$

In other words, suppose we have unlimited copies of the following $n$ items, $\{\{w_0,v_0\},\{w_1,v_0\},...,\{w_n,v_n\}\}$. Assume now that the optimal solution contains some item $x_i$. Then we will see that $K[x-w_i] = k[x] - v_i$, meaning that the optimal solution for $K[x]$ contains within it optimal solutions to smaller subproblems.

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 $W$ and suppose that we have unbounded copies of $n$ items available to us. Now suppose that we know the optimal value to the knapsack is $K[W]$ and that the optimal solution contains one copy of item $x_k$ for some natural number $k$. We claim that $K[W] - v_k$ is an optimal value for a knapsack of size $W - x_k$. That is, $K[W - x_k] = K[W] - v_k$.

We will prove our claim by contradiction. Suppose that $K[W] - v_k$ is not an optimal value and that the optimal value is $T^{\prime}$. Since we know that the optimal solution to the knapsack of size $W$ contains a copy of item $x_k$, we can therefore add $x_k$ to $K[W - x_k]$ to obtain an optimal value $T^{\prime} + v_k$. But $T^{\prime} + v_k > K[W] - v_k + v_k = K[W]$. This is a contradiction since we assumed that $K[W]$ is an optimal value. Therefore, $K[W] - v_k$ must be an optimal value for a knapsack of size $W - x_k$. $\blacksquare$

Running Time

Assume we have $n$ items and the knapsack is of size $W$. The runtime is $O(nW)$.

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, $W=9$. The optimal solution is to pack a taco and an enchilada for a total value of 27.

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 $2^n$ possible subsets to check and the running time is $O(2^n)$.

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 $x$, the larger problem must know not to re-take it which is a violation to the constraint of having one copy only per 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 $x$ to indicate the knapsack size and $y$ to indicate that we’re using the first $y$ items.

Suppose we know the optimal solution to $K[x,y]$ for a knapsack of size $x$ using items $0,..y$.
There are two cases:
Case 1: $K[x,y]$ does not use item $y$. In this case, $K[x,y] = K[x,y-1]$.
Case 2: We do use item $y$. In this case, we claim that $K[x,y] = K[x-w_y,y-1] + y_k$.
We can therefore, summarize it in:

$$ \begin{align*} K[x,y] = \max\{K[x, y-1], K[x - w_y, y-1] + v_y\} \end{align*} $$

With the base case of $K[x,0]=0$ and $K[0,y]=0$.

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

References

Stanford CS161