← All patterns
22 / 29
Dynamic Programming

Knapsack DP

💰
Picture this

In the vault, a thief weighs every jewel against a fixed-size sack, packing for maximum worth without bursting it.

When you see it

Signal words

If the prompt uses any of these, this pattern should come to mind first.

subset sumpartitioncoin changetarget sumcapacitychoose items

Ask yourself

  1. Choose a subset under a capacity/target?
  2. Coin change / partition / subset-sum?
  3. dp over (item, remaining capacity).

Canonical template

const dp = Array(cap + 1).fill(0);
for (const [weight, value] of items) {
  for (let c = cap; c >= weight; c--) {
    dp[c] = Math.max(dp[c], dp[c - weight] + value);
  }
}
return dp[cap];

Common pitfalls

Iterating capacity upward for 0/1 (double-counts items).

Confusing bounded vs unbounded knapsack loops.