Knapsack DP
The Intuition
Imagine you're packing a backpack for a weekend hike. You've laid out everything on the floor: a heavy jacket (3 kg, warmth value 7), a book (1 kg, entertainment value 4), trail mix (2 kg, nutrition value 5), binoculars (2 kg, utility value 3), and a pillow (3 kg, comfort value 2). Your backpack holds at most 5 kg. Which items do you grab to get the most total value?
For each item, you make a binary choice: take it or leave it. If you take the jacket (3 kg), you only have 2 kg left for everything else. If you leave it, you still have 5 kg. The best answer depends on what you'd do with the remaining capacity after each choice. That recursive structure, "best value with capacity w," is what dp[w] captures.
Picture filling out a row of slots labeled 0 through 5, one for each possible kilogram of capacity. dp[0] = 0 because an empty backpack carries nothing. For each item, you walk through the capacity slots and ask: "would including this item at this capacity beat what I already have?" If the jacket weighs 3 and is worth 7, then dp[5] might improve to dp[5-3] + 7 = dp[2] + 7. You're leveraging the answer for a smaller backpack to build the answer for a larger one.
Here's the subtle part. For 0/1 knapsack, where you can only take each item once, you process the capacity slots from right to left. Why? Because if you go left to right, you might use the updated dp[2] (which already includes the jacket) to compute dp[5], accidentally packing the jacket twice. Going right to left ensures you're always looking at values from before you considered the current item. For unbounded knapsack (unlimited copies of each item), you WANT that left-to-right propagation because reusing an item is allowed.
Subset selection with a weight or sum constraint, minimizing/maximizing a value under capacity limits, counting combinations that reach a target sum, or partitioning a set into groups with equal or bounded sums.
Items are divisible/fractional (use greedy fractional knapsack), constraint count is more than 2 (multi-dimensional DP, different approach), or item count is small enough for bitmask (use bitmask DP).
Variations:
- 0/1 Knapsack: Each item chosen at most once. Iterate capacity in reverse.
- Unbounded Knapsack: Items can be reused. Iterate capacity forward.
- Bounded Knapsack: Each item has a limited count. Use binary decomposition to reduce to 0/1.
- Subset Sum: A special case where values equal weights and you check reachability.
- Counting variants: dp[w] counts the number of ways instead of the optimal value.
- Multi-dimensional Knapsack: Multiple constraints (e.g., weight and volume) require a multi-dimensional dp array.
- Capacity is 0, so no items can be selected and the answer is the base case
- A single item whose weight exceeds the capacity
- All items have the same weight, simplifying the decision to a count
- Target sum is negative or exceeds the total sum of all elements
- Items with zero weight or zero value that could cause infinite loops in unbounded variants
- Very large capacity requiring space optimization (1D dp array)
- When counting combinations vs permutations, the loop order over items and capacity matters
Key Points
- •0/1 knapsack: each item used at most once, iterate weights in reverse
- •Unbounded knapsack: each item used unlimited times, iterate weights forward
- •1D array optimization reduces space from O(n*W) to O(W)
- •dp[w] represents the optimal value achievable with capacity w
- •Many problems reduce to knapsack: subset sum, coin change, partition
Code Template
1 def knapsack_01(weights, values, capacity):
2 """0/1 Knapsack: each item can be used at most once.
3 Returns maximum total value within capacity."""
4 n = len(weights)
5 dp = [0] * (capacity + 1)
6
7 for i in range(n):
8 # Reverse order prevents using the same item twice
9 for w in range(capacity, weights[i] - 1, -1):
10 dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
11
12 return dp[capacity]
13
14 def knapsack_unbounded(weights, values, capacity):
15 """Unbounded Knapsack: each item can be used any number
16 of times. Returns maximum total value within capacity."""
17 dp = [0] * (capacity + 1)
18
19 for i in range(len(weights)):
20 # Forward order allows reusing the same item
21 for w in range(weights[i], capacity + 1):
22 dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
23
24 return dp[capacity]
25
26 def subset_sum(nums, target):
27 """Check if any subset sums to target (0/1 knapsack)."""
28 dp = [False] * (target + 1)
29 dp[0] = True
30
31 for num in nums:
32 for t in range(target, num - 1, -1):
33 dp[t] = dp[t] or dp[t - num]
34
35 return dp[target]
36
37 def coin_change_min(coins, amount):
38 """Minimum coins to make amount (unbounded knapsack)."""
39 dp = [float('inf')] * (amount + 1)
40 dp[0] = 0
41
42 for coin in coins:
43 for a in range(coin, amount + 1):
44 dp[a] = min(dp[a], dp[a - coin] + 1)
45
46 return dp[amount] if dp[amount] != float('inf') else -1Common Mistakes
- Iterating weights in the wrong direction for 0/1 vs unbounded variants
- Off-by-one in capacity bounds when items have zero weight
- Forgetting to initialize dp[0] properly (0 for optimization, 1 for counting)
- Not recognizing a problem as a knapsack variant in disguise