The Knapsack Family

The 10-second versionCopy Anchor Link

You have items, each with a weight and a value, and a bag that holds a fixed capacity. Pick a subset of items to maximise total value without going over capacity. The whole algorithm is a one-dimensional array dp[c] = "best value achievable with a budget of c", updated once per item. There are two flavours: 0/1 knapsack (each item at most once) and unbounded knapsack (unlimited copies of each). They differ by exactly one character — the direction you sweep c — and getting that backwards is the most famous off-by-a-loop bug in dynamic programming. Subset-sum and the partition problem are this same idea wearing a "values are all 1" costume.

Why this existedCopy Anchor Link

Picture a merchant in the 1950s with a problem that has nothing to do with hiking. A trading-stamp catalogue offers items at different point values; a customer has a fixed number of points to spend and wants the most value for them. Pick the best combination. That's a knapsack. George Dantzig wrote the problem down in 1957 and gave it the name we still use — a hiker filling a knapsack of fixed capacity with the most valuable selection of items.

The twist that makes it interesting is indivisibility. If you're allowed to take fractions of an item — half a gold bar — the problem is easy, and greedy is provably optimal: sort by value-per-kilo and take the best ratio until the bag is full. The moment items are indivisible (each one either goes in or it doesn't), greedy breaks, and the problem becomes NP-hard: there is no polynomial-time algorithm in the number of items unless P = NP.

Why care about a hard problem? Because around the same time Richard Bellman was formalising dynamic programming as a general tool for sequential decisions, and the knapsack turned out to be its poster child — not polynomial in the number of items, but perfectly solvable in time proportional to the number of items times the capacity. It's the first place you feel the difference between "hard in the size of the input" and "hard in the numeric value of the input," which we now call pseudo-polynomial.

And it was not just theory. In 1978 Merkle and Hellman built a public-key cryptosystem whose secret key was a hidden knapsack. Shamir broke it in 1982, but it made "subset-sum" a phrase every security engineer knows.

Why it mattered then: it was the first crisp example of a problem that is genuinely hard in general yet completely tractable for real capacities — a lesson that reshaped how people thought about "hard."

Inside the inventor's headCopy Anchor Link

The first instinct is brute force: every item is either in or out, so try all 2ⁿ subsets and keep the best one that fits. Correct, and hopeless past about thirty items.

The second instinct is greedy: rank items by value-per-weight and take the best ones first. For the fractional knapsack this is optimal — and that's exactly the trap, because it makes you believe it always works. Watch it fail on 0/1. Capacity 10, three items: (weight 6, value 6), (weight 5, value 5), (weight 5, value 5). Every item has the same ratio 1, so greedy grabs the 6/6 item first, fills 6 of the 10 units, and can't fit either 5-weight item — total value 6. The optimal answer takes both 5-weight items for value 10.

Here's that greedy in code — correct for fractional, wrong the moment items are whole:

// Correct for the fractional knapsack; wrong once items are indivisible.function fractional(items, cap) {  const sorted = [...items].sort((a, b) => b.v / b.w - a.v / a.w);  let total = 0;  for (const it of sorted) {    if (cap <= 0) break;    const take = Math.min(it.w, cap);    total += take * (it.v / it.w);    cap -= take;  }  return total;}

So the pivot is the one you now expect: stop thinking about items and start thinking about capacity. Ask a smaller, blessedly one-dimensional question — "what is the best value I can get with a budget of exactly c?" — then stream the items past that answer one at a time. The only subtlety, the thing that trips up literally everyone the first time, is the direction you sweep c in. We'll get there in a moment.

The final approachCopy Anchor Link

The stateCopy Anchor Link

Let dp[c] be the maximum value obtainable with a capacity budget of c. One dimension, over capacity. Start with dp[c] = 0 for every c — selecting nothing is worth nothing.

Process items one at a time. For a single item of weight w and value v, the only question is whether including it beats not including it:

dp[c] = max(dp[c], dp[c - w] + v)      for every c from w up to capacity

That's the whole update. The dp[c] on the right is "best without this item"; dp[c - w] + v is "best with it, spending w of the budget." Take the bigger.

The trap: which way do you sweep c?Copy Anchor Link

This part deserves a diagram, because it's the entire 0/1-versus-unbounded distinction.

Subtracting w jumps backwards in c. If you're sweeping upwards, then by the time you reach index c you have already overwritten dp[c - w] with the result for the current item — so the current item quietly gets used again and again, and you've accidentally solved the unbounded problem. Sweeping downwards means dp[c - w] still holds the untouched previous-item value, so the item can be counted only once. That single direction flip is the difference between 0/1 and unbounded, and it is the classic subtle bug.

The invariantCopy Anchor Link

After processing the first k items, dp[c] equals the best value using any subset of those k items within capacity c. The 0/1 sweep maintains this because dp[c - w] never reflects the current item (it's still on the previous item's row); the unbounded sweep maintains it precisely because dp[c - w] does reflect the current item — that's what "unlimited copies" means. Same loop body, opposite invariant satisfied by the same expression read in two directions.

A worked traceCopy Anchor Link

Capacity 5, items (w=1, v=1), (w=3, v=4), (w=4, v=5), (w=5, v=7), 0/1, so we sweep c downward for each item.

The answer is dp[5] = 7, from the single (5, 7) item. Watch dp[5] after the (4, 5) item: it became 6 by pairing (1, 1) with (4, 5). Then the (5, 7) item beat it with a clean 7. Notice that the row for (5, 7) was computed by scanning c = 5 downward — only one cell — while earlier rows swept across several.

Here is the full implementation. The 0/1 and unbounded variants live in one function, and the only thing that changes is for (c = cap; c >= w; c--) versus for (c = w; c <= cap; c++):

function knapsack01(w, v, cap) {  const dp = new Array(cap + 1).fill(0);  for (let i = 0; i < w.length; i++)    for (let c = cap; c >= w[i]; c--)              // sweep DOWN      dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);  return dp[cap];}function knapsackUnbounded(w, v, cap) {  const dp = new Array(cap + 1).fill(0);  for (let i = 0; i < w.length; i++)    for (let c = w[i]; c <= cap; c++)              // sweep UP      dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);  return dp[cap];}

Cousins: subset-sum and partitionCopy Anchor Link

Set every value to 1 and ask "which sums are reachable?" and you have subset-sum — a boolean knapsack: dp[c] is true if some subset of the items sums to exactly c. The update becomes dp[c] = dp[c] || dp[c - x], swept downward (0/1), starting from dp[0] = true. The partition problem — can this array be split into two groups of equal sum? — is subset-sum with target total / 2: if the total is odd it's an instant no, otherwise ask whether a subset sums to exactly half.

function subsetSum(a, target) {  const dp = new Array(target + 1).fill(false);  dp[0] = true;  for (const x of a)    for (let c = target; c >= x; c--)             // 0/1: sweep DOWN      if (dp[c - x]) dp[c] = true;  return dp[target];}function canPartition(a) {  const total = a.reduce((s, x) => s + x, 0);  if (total % 2 !== 0) return false;  return subsetSum(a, total / 2);}

ComplexityCopy Anchor Link

Both loops visit every (item, capacity) pair once, so best and worst coincide. The word pseudo-polynomial is the whole point: W is a value, not a count, so an array of weights like 10⁹ is efficient while the same input written in unary is not. That gap is exactly why knapsack is NP-hard despite this neat table.

Where you meet it todayCopy Anchor Link

• Budget and cargo allocation. "Maximise shipped value under a weight limit" is 0/1 knapsack; the dp[capacity] array is small enough to run live in a shipping dashboard.
• Coin change and currency. "Fewest coins for this amount" and "how many ways to make change" are unbounded knapsack with value standing in for cost — the forward sweep.
• Load balancing and fair division. Assigning jobs or assets to two roughly-equal halves is the partition problem; the classic "can two players split these without a fight?" test.
• Cryptography, again. Subset-sum was the secret in the Merkle–Hellman cryptosystem, and subset-sum instances still show up in lattice-based attacks and benchmarks.

Here's the coin-change cousin in miniature — unrestricted copies, so the loop runs forward:

function minCoins(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;  for (const coin of coins)    for (let c = coin; c <= amount; c++)          // unlimited copies: sweep UP      dp[c] = Math.min(dp[c], dp[c - coin] + 1);  return dp[amount];}

RecapCopy Anchor Link

• The state is a single capacity budget: dp[c] = best value with capacity c.
• 0/1 knapsack sweeps c downward so dp[c - w] stays on the previous item's row — each item is used at most once.
• Unbounded knapsack sweeps upward so dp[c - w] already includes the current item — reuse is allowed. That direction is the only difference.
• Subset-sum and partition are knapsack with all values equal to 1; the same downward sweep makes them 0/1.
• The O(n · capacity) cost is pseudo-polynomial — fast for small capacities, helpless when the numbers are astronomically large.

Next up: Longest Increasing Subsequence — where the state is a position, and a clever tails array turns a quadratic DP into a fast one.