MPCS 55001 — Lecture 10

Since we sort of walked our way through the weighted interval problem without having the overall approach in mind, let's do a quick review of how to approach a problem using dynamic programming.

1. Identify the subproblems that make up a solution to your overall problem.
2. Prove a recurrence relation for these subproblems.
3. Use the recurrence in an algorithm that iteratively solves the subproblems.
4. Prove that your algorithm works by a straightforward induction.

Knapsack

On Problem Set 2, you were presented with a variant of a knapsack problem, where you were allowed to schedule YouTubers for arbitrary portions of time if you wished. This was solved using a greedy algorithm, but then you were asked to show that your greedy algorithm would not work if you weren't allowed to divide time up arbitrarily; i.e. you had to either schedule someone for all of their time or none of it.

Here, we will be investigating the second, more common formulation of the knapsack problem, which couldn't be solved with a greedy algorithm.

Problem 10.1. 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.

The knapsack problem was first formulated by Dantzig in 1957 and he gives a basic dynamic programming algorithm for it. 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.

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

Example 10.2. 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.

Definition 10.3. 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 \[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. Suppose that $w_i \gt w$. Then $i \not \in \mathcal O_{i,w}$, since choosing $i$ would exceed our allowed weight. Then $\mathcal O_{i,w}$ must contain only items chosen from $1, \dots, i-1$. Therefore, $OPT(i,w) \leq OPT(i-1,w)$. On the other hand, we have $OPT(i,w) \geq OPT(i-1,w)$, since we can choose $\mathcal O_{i,w} = \mathcal O_{i-1,w}$. Thus, we have $OPT(i,w) = OPT(i-1,w)$.
2. Suppose $w_i \leq w$.
   1. If $i \not \in \mathcal O_{i,w}$, then similar to the above, $\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. In other words, we have $OPT(i,w) \leq v_i + OPT(i-1,w-w_i)$. And by taking $\mathcal O_{i,w} = \mathcal O_{i-1,w-w_i} \cup \{i\}$, we have $OPT(i,w) \geq v_i + OPT(i-1,w-w_i)$, 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.

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

This recurrence leads to the following algorithm.

    \begin{algorithm}
    \caption{Compute Knapsack $OPT(i,w)$}
    \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}
    \end{algorithm}

Example 10.6. 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.

Proposition 10.7. Algorithm 10.5 computes $OPT(n,W)$.

Proof. We will show that $V[i,w] = OPT(i,w)$ for $i \leq n$ and $w \leq W$ by induction on $(i,w)$. First, we consider as our base cases $i = 0$ and $w = 0$. We have that $V[0,w] = 0 = OPT(0,w)$ for all $w \leq W$ and $V[i,0] = 0 = OPT(i,0)$ for all $i \leq n$.

Now consider $i,w \gt 0$ and assume that for all $(i',w')$ that are computed before $(i,w)$ that $V[i',w'] = OPT(i',w')$. First, suppose $w_i \gt w$. Then by line 7, we have $V[i,w] = V[i-1,w]$. By our inductive hypothesis, $V[i-1,w] = OPT(i-1,w)$, so $V[i,w] = OPT(i-1,w)$ and therefore $V[i,w] = OPT(i,w)$ as desired.

Then if $w_i \leq w$, by line 9, we have \[V[i,w] = \max(V[i-1,w], v_i + V[i-1,w-w_i])\] and by our inductive hypothesis, we have \[V[i,w] = \max\{OPT(i-1,w), v_i + OPT(i-1,w-w_i)\},\] so $V[i,w] = OPT(i,w)$. $$\tag*{$\Box$}$$

Proposition 10.8. Algorithm 10.5 has running time $O(nW)$.

Proof. The work is done in the nested loops. Each of the computations within the loops can be done in $O(1)$ time. The inner loop is run $W$ times, while the outer loop is run $n$ times. This gives $O(nW)$ time in total. $$\tag*{$\Box$}$$

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.