Knapsack

One lump credit, forty refunds

A partner bank sends one credit of ₹48,500 with a one-line note: "returned refunds, batch 17". Forty refunds are waiting to be matched, each a whole number of rupees, and finance needs to know whether some of them add up to exactly ₹48,500 before the books close on Friday.

The obvious script tries every subset of the 40. It is correct, and it prints a progress line every million subsets. Do the sum before reading on. 2⁴⁰ is 1,099,511,627,776 subsets. At a million a second that is about 12.7 days. Friday is in two.

The script keeps track of which refunds are in each subset, but finance only asked whether some set of refunds makes ₹48,500. Two different subsets that both add up to ₹20,000 are interchangeable for every refund that comes after them, because only the total matters. And there are only 48,501 possible totals from ₹0 to ₹48,500.

Pause and predict What should the script keep one cell for?

One row of capacities, updated item by item

Can some of the numbers [2, 3, 5] add up to 7? Trying every subset takes 2ⁿ checks. But the question only cares about sums, and there are only eight sums from 0 to 7, so keep one cell per sum.

This is dynamic programming with a second part in the state: a capacity, or a sum to reach. The full table is dp[i][c], with one row per item and one column per capacity, as in the 2D unit. Row i reads only row i - 1, so a single row is enough: dp[c], rewritten once for each item.

Which way the capacity loop runs

On a single row, whether a cell still holds its old value depends on the order of the loop. If the loop reads a cell before overwriting it, the value is old. If it reads the cell after overwriting it, the value already includes item i.

Pause and predict Items [3, 5], each usable once. The loop runs the capacity up, c = 3, 4, 5, 6, with dp[c] = dp[c] or dp[c - w]. Does the row end up saying 6 is reachable?

Which loop is outside

For a yes-or-no answer or a minimum, putting either loop outside gives the same answer. For counting ways, the choice decides what you count.

Pause and predict Coins [1, 2, 3], amount 4, counting with the amount loop outside and the coins inside. What comes out?

Min, count, or reachable

The loops stay the same in every version. Only the way the two old cells are combined changes. To ask whether a sum is reachable, combine them with OR. To count the ways, add them. To find the fewest items, take the smaller of dp[c] and dp[c - w] + 1. That last version is Coin Change, and it shows why a greedy rule that always takes the largest coin is not enough. To make 8 from [1, 4, 5], the greedy takes 5 + 1 + 1 + 1, four coins, while the table finds 4 + 4, two coins. The table tries every possible last coin, while the greedy commits to one.

How to recognise it

Ask two questions. Is there a budget or a target number? And is each choice whether to use an item, or how many copies of it to use? If both answers are yes, the capacity belongs in the state.

Pause and predict Target Sum: put + or - before each number so the total hits a target. What is it underneath?

Three that only look like it

• A state that is only a position. Robbing houses and climbing stairs have no amount to track, so they are plain 1D DP.
• A request to list every combination that hits the target. The output itself can be exponentially long, so list them with backtracking. A knapsack table answers "is there one", "how many" or "how few", and cannot list them all.
• A choice that never needs undoing. With coins of 1, 5, 10 and 25, a greedy rule works, but only because it can be proved for those coins. For arbitrary coins it fails.

Where it bites

Pause and predict Java, Coin Change with "impossible" as Integer.MAX_VALUE. What is Math.min(5, Integer.MAX_VALUE + 1)?

• Running the capacity loop in the wrong direction. Going up on a 0/1 problem reuses an item: [1, 2, 5] appears to split into two equal halves, because the table makes 4 as 1 + 1 + 1 + 1. Going down on an unbounded problem forbids reuse.
• Putting the wrong loop outside when counting. With the amounts outside, the table counts orders: 7 instead of 4 for amount 4 from [1, 2, 3].
• Leaving out the base. Counting needs dp[0] = 1, and reachability needs dp[0] = true. Both stand for the empty choice. Without the base, every cell stays 0 or false.
• Skipping the checks before building the table. In Partition, an odd total means the answer is false. In Target Sum, an odd total + target, or |target| > total, means the answer is 0.
• Getting a range off by one. In Python, range(half, w - 1, -1) includes w. range(half, w, -1) stops before w, so a number can never be used on its own to make its own value.