CMSC 27200 — Lecture 16

Knapsack

The knapsack problem was first formulated by Dantzig in 1957 and he gives a basic dynamic programming algorithm for it. The idea is that you have a knapsack that can hold a certain amount of weight. You would like to fill it with items such that the value of the items you choose are maximized. Of course, we don't really care about filling literal knapsacks full of stuff—this just happens to be a useful metaphor.

Dantzig is well known for the Simplex algorithm for solving linear programming problems. He is also the source of the urban legend of the student who was late to class, copied down some equations, did them for homework, and inadvertently solved two unsolved problems: he was the (grad) student.

The 0-1 knapsack problem is given a list of $n$ items, where item $i$ has value $v_i \gt 0$ and weight $w_i \gt 0$, and a knapsack weight limit of $W$, choose the subset of items with the maximum total value.

For this problem, we will assume that values and weights are positive integers.

Consider the following items.

Suppose we can carry weight $12$. Then $\{1,5\}$ has weight 12 and value 20, while $\{1,3,4\}$ has weight 11 and value 22.

The question is, similar to our greedy algorithm, how should we consider how to choose items? We can look for greedy algorithms for a bit of inspiration: do we choose based on weight? On value? On weight and value?

We can think through similar choices. We want to maximize the value of a solution to the problem, but the question is which choices we should be making. Suppose that we only consider the optimal value of a solution by considering the items $1, \dots, i$. This seems like it should work, but there is a crucial piece missing: how do we ensure that we don't exceed our weight limit? Similarly, we can try to optimize around the value of a solution considering only the possible weight, but how do we formulate how this changes with respect to each item that's chosen?

It turns out the answer is to do both.

Let $OPT(i,w)$ denote the value of an optimal solution $\mathcal O_{i,w}$ for the knapsack problem on items $1, \dots, i$ subject to weight limit $w$.

In essence, what we do is to consider two different subproblems at the same time: the subproblem of which items are chosen out of $1, \dots, i$ and the subproblem of which items to choose with the given weight limit $w$. The subproblem of selecting a subset of items $1, \dots, i$ is clear, since it's similar to the scheduling problem we saw earlier.

But how do we consider subproblems on weight? Luckily, we made the helpful assumption that all weights are integers, so we have subproblems ranging on $0 \leq w \leq W$. This gives us the equation with two variables, \[OPT(i,w) = \max_{S \subseteq \{1,\dots,i\}} \sum_{j \in S} v_j \quad \text{subject to } \sum_{j \in S} w_j \leq w.\]

Under this formulation, we want to compute $OPT(n,W)$. So, now we need to figure out how to express $OPT(i,w)$ in terms of smaller subproblems. Let us consider what our choices are regarding $OPT(i,w)$ when considering whether $i \in \mathcal O_{i,w}$.

1. If $i \not \in \mathcal O_{i,w}$, then $\mathcal O_{i,w}$ must contain only items chosen from $1, \dots, i-1$, and we have $OPT(i,w) = OPT(i-1,w)$.
2. If $i \in \mathcal O_{i,w}$, then this means that $v_i$ is added to our solution and we must add the weight $w_i$, which decreases the allowed weight in any subproblem. So we have $OPT(i,w) = v_i + OPT(i-1,w-w_i)$.

We then take $OPT(i,w) = \max\{OPT(i-1,w), v_i + OPT(i-1,w-w_i)\}$.

This gives us the following recurrence, which we'll prove formally.

$OPT(i,w)$ satisfies the following recurrence. \[OPT(i,w) = \begin{cases} 0 & \text{if $i = 0$ or $w = 0$}, \\ \max\{OPT(i-1,w), v_i + OPT(i-1,w-w_i)\} & \text{for $i,w \gt 0$}. \end{cases} \]

This recurrence leads to the following algorithm.

    \begin{algorithmic}
    \PROCEDURE{knapsack}{$W,I = \{(w_i,v_i) \mid 1 \leq i \leq n\}$}
        \FOR{$w$ from $1$ to $W$}
            \STATE $V[0,w] \gets 0$
        \ENDFOR
        \FOR{$i$ from $1$ to $n$}
            \FOR{$w$ from $0$ to $W$}
                \IF{$w_i \gt w$}
                    \STATE $V[i,w] \gets V[i-1,w]$
                \ELSE
                    \STATE $V[i,w] \gets \max\{V[i-1,w],v_i + V[i-1,w-w_i]\}$
                \ENDIF
            \ENDFOR
        \ENDFOR
        \RETURN{$V[n,W]$}
    \ENDPROCEDURE
    \end{algorithmic}

Recall Example 10.2 from above. Running this algorithm constructs the following table $V$.

Our solution, $OPT(n,W)$, is highlighted in red. This table also gives us a way to figure out which items were chosen: if $V[i,w] \gt V[i-1,w]$, then item $i$ was chosen.

knapsack computes $OPT(n,W)$.

knapsack has running time $O(nW)$.

Now, at this point, some of you may remember my note on the solution to this problem that there is no known polynomial time algorithm for knapsack, but here, we have an algorithm that runs in $O(nW)$ time! What's up with that?

The key here is to remember that the complexity of algorithms are functions of the size of the input, so it's worth stepping back to ask what the size of this problem instance is. One part is obvious: the number of items that we have. The other part is not so obvious: what is the size of $W$?

A common mistake, as in this case, is to take $W$ as the size of $W$. But $W$ is the input, a number. The size of $W$ is the size of its representation, which is the number of bits of $W$ (or digits if you prefer to use some other number system). Either way, for any representation that isn't unary, the size of $W$ is $O(\log W)$.

The issue here then becomes clear: $W$ is not polynomial in $\log W$, so our $O(nW)$ bound is not polynomial in the size of the input. Algorithms that are polynomial in the numeric value of the input but not the size of the input are said to be pseudopolynomial.

Knapsack problems belong to a family of packing problems, where we are given a set of items with various properties and constraints and we are asked to choose a selection of items subject to constraints while tying to maximize or minimize some property:

• The subset sum problem: Given a set $S$ of $n$ integers and an integer $N$, what is the largest subset of $S$ whose members add up to at most $N$? This is 0-1 knapsack, but with $v_i = w_i$.
• The bounded/unbounded knapsack problem: The same as 0-1 knapsack, but you can choose more than one of each item.
• The multidimensional knapsack problem: The same as 0-1 knapsack, but with more constraints than just weight.
• The bin packing problem: Given a set $S$ of items, each with size $s_i$ and bins of size $B$, partition $S$ into subsets of size at most $B$, while minimizing the number of subsets (i.e., put your things into the least number of bins possible).
• The cutting stock problem: Similar to the bin packing problem, but instead of minimizing the number of bins, you want to minimize the amount of unused space in each "bin". This is called the cutting stock problem because it's derived from a problem from problems where you have to cut paper rolls into various sizes from a standard size.

It becomes pretty clear that many of these problems are quite important, in that they can be repurposed very easily as various computational and real life applications. However, they also happen to share the same unfortunate downside: we don't have efficient algorithms for many of these problems. This is where we begin to see glimpses of intractability rear its ugly head.