Knapsack Problems

In House Robber each house had two options: rob it or skip it. The knapsack problem is almost the same. Each item has two options: take it or leave it. The one new element is a capacity limit: the weights of the items you take must add up to no more than the capacity of the bag. Pack the bag yourself first and see how the limit changes the decisions.

What does brute force cost? Each item is taken or not, so n items give 2ⁿ subsets. Checking every subset's weight and value is about a billion steps at n = 30, which is far too slow. That is the same growth as the backtracking tree in Chapter 5. Why can it be improved? Because the same subproblem is asked many times. "The best value from the first 3 items with capacity 5" is reached by many different decision paths, and the answer is the same every time. Overlapping subproblems plus optimal substructure — the best answer for a smaller capacity is part of the best answer for a larger one — are exactly the two conditions DP needs.

Follow the five steps from Chapter 7. Define the state in words first: dp[i][j] = the largest value you can reach when only the first i items are available and the total weight is at most j. Then write the transition. Standing in front of item i, there are exactly two options:

• Skip it: the value is the best you could do with the first i−1 items and the same capacity j, which is dp[i−1][j].
• Take it: first free w[i] of capacity, then add its value, which is dp[i−1][j−w[i]] + v[i]. This option only exists when j ≥ w[i].

Take the larger of the two. Base case: row 0 is all zeros, because with no item available the value is 0 at every capacity. The answer is dp[n][W], the bottom-right cell. Watch the table fill in, cell by cell. A dashed blue cell is a value the current cell reads.

Look at the transition again: dp[i][j] reads only two cells, and both are in the previous row. Once row i−1 has been used, it is never needed again. So there is no reason to keep the whole table. Keep one row and overwrite it. The two-dimensional dp[i][j] becomes the one-dimensional dp[j], and each item is one full sweep of that row. After the sweep the row holds exactly the numbers of the matching table row.

Rolling the table introduces one question that did not exist before. When the sweep writes dp[j], it reads dp[j−w]. Is that the old value from the previous row, or a value this same sweep has already overwritten? In the 0/1 knapsack the transition needs dp[i−1][j−w], which is the old value — the state in which this item has not been used yet. The direction of the sweep is what decides which of the two you get. Switch between the two buttons below: same item, same array, two directions.

The problem: given an array of positive integers, can it be split into two subsets with equal sums? The reduction: if the two sums are equal, each one is sum/2. So an odd total makes a split impossible. Otherwise the question becomes: can some of the numbers add up to exactly sum/2? That is a 0/1 knapsack — each number is an item used at most once, sum/2 is the capacity — but instead of the largest value it asks whether the bag can be filled exactly.

Why does the same code work? Because "largest value" and "can it be filled" use the same take-or-skip skeleton. Only the operator changes, from max to boolean or: dp[j] = "j was already reachable" || "j−num was reachable and we add one num". Nothing here is a new algorithm; it is the same table with a boolean in each cell.

The problem: put a + or a − in front of every number in nums so the expression equals target, and count how many ways there are. As backtracking: each number has two options, so the search is a binary decision tree of depth n. Walk to the bottom and count the leaves whose sum is target. The logic is right, but the cost is O(2ⁿ):

How does this become a knapsack? Through one algebraic step. Let P be the sum of the numbers that get a plus sign, and N the sum of the absolute values of the rest. Then:

The rest is the LC 416 skeleton with the boolean or replaced by addition of counts: dp[j] += dp[j−num]. The number of ways to make j is the ways already counted, plus the ways to make j−num followed by this num. Base case dp[0] = 1, because the empty subset is one way to make 0. The capacity still runs downward, because each number is used at most once.

The problem: given a list of binary strings and a budget of at most m zeros and n ones, how many strings can you choose? The observation: each string is a 0/1 item, but it spends two resources at once — the zeros it contains and the ones it contains. That is a two-cost knapsack: two limits instead of one, so the table gets one more dimension.

State: dp[i][j] = the largest number of strings you can choose using at most i zeros and j ones. The transition is still take-or-skip this string; the only change is that taking it frees two kinds of capacity: dp[i][j] = max(dp[i][j], dp[i−zeros][j−ones] + 1). Each string is still used at most once, so both capacity loops run downward, for exactly the reason given in §03.

In an unbounded knapsack each item may be taken any number of times. Recall why going up was wrong in §03: dp[j−w] had already been updated in the same sweep, so it already contained one copy of the item, and the item was counted twice. For the unbounded knapsack that is not a bug — reusing an item is exactly what the problem allows. So the code is the 0/1 code with one direction reversed.

The two-dimensional form makes the same distinction visible in one character. The 0/1 transition is dp[i][j] = max(dp[i−1][j], dp[i−1][j−w] + v). The unbounded transition is dp[i][j] = max(dp[i−1][j], dp[i][j−w] + v) — it reads its own row, the row in which item i may already have been taken. Rolling each of them into a single array gives exactly the two directions above: reading the previous row means reading a cell this sweep has not touched, which is the descending order, and reading the current row means reading a cell this sweep has already written, which is the ascending order.

LC 322 Coin Change makes a good test, because Chapter 7 already solved it a different way: there, dp[amount] was filled by asking which coin is the last one. Here the model is an unbounded knapsack — coins are items with unlimited supply, the amount is the capacity — and the array is filled one coin type at a time, ascending. Two models, one answer:

Counting problems on the unbounded knapsack have one detail that is easy to get wrong. Two problems can both ask "how many ways make the amount n", both use dp[j] += dp[j−coin], and still count different things, because of the order of the two loops.

Start with LC 518, combinations: coins = [1,2,5] and amount 5. Coins on the outside means the passes happen in a fixed order — first count every way that uses only ¥1, then bring in ¥2, then ¥5. ¥2 always enters after ¥1, so no way is ever counted twice under a different ordering. Step through it: