AdvancedData Structures & Algorithms · Lesson 35 of 40 · Updated ·
0/1 Knapsack and Subset Sum — Take It or Leave It DP
You are packing a bag for a college trek. The bag holds at most 7 kg. Each item has a weight and a value (how useful it is), and you can take each item at most once. Which items give the largest total value without going over 7 kg? This is the 0/1 knapsack problem: for each item the choice is 0 (leave it) or 1 (take it). The same "take it or leave it" choice is behind subset sum, equal partition, target sum and many budget problems in placement tests.
1. Why greedy fails
A natural idea is to sort items by value per kg and take the best ones first. Try it on these four items with capacity 7:
| Item | Weight | Value | Value per kg |
|---|---|---|---|
| A | 1 | 1 | 1.00 |
| B | 3 | 4 | 1.33 |
| C | 4 | 5 | 1.25 |
| D | 5 | 7 | 1.40 |
Greedy takes D first (best ratio), leaving 2 kg. B and C no longer fit, so it adds A: total value 8. But B + C weighs exactly 7 and is worth 9. Taking one "good" item blocked a better pair. Because items cannot be cut into pieces, we must compare whole combinations, and DP does that without trying all 2ⁿ subsets.
(If items can be cut, like rice or sugar sold by weight, the problem is called fractional knapsack and greedy by ratio is correct. Do not mix the two up.)
2. The 2D table
- State:
dp[i][c]= best value using only the firstiitems with capacityc. - Recurrence: for item
i(weightw, valuev) there are two choices:- skip it:
dp[i − 1][c]; - take it (only if
w ≤ c):v + dp[i − 1][c − w]. dp[i][c]is the larger of the two.
- skip it:
- Base:
dp[0][c] = 0— with no items the value is 0. - Answer:
dp[n][W], the bottom-right cell.
Read the table row by row. Each new row asks only "is this item worth taking at this capacity?", using the row above. To find which items were taken, walk up from the bottom-right: if dp[i][c] differs from dp[i − 1][c], item i was taken, so subtract its weight and continue.
def knapsack(wt, val, W):
n = len(wt)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = wt[i - 1], val[i - 1]
for c in range(W + 1):
dp[i][c] = dp[i - 1][c] # skip item i
if w <= c:
dp[i][c] = max(dp[i][c], v + dp[i - 1][c - w]) # take it
taken, c = [], W
for i in range(n, 0, -1): # walk back up
if dp[i][c] != dp[i - 1][c]:
taken.append(i - 1)
c -= wt[i - 1]
return dp[n][W], sorted(taken)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(knapsack([10, 20, 30], [60, 100, 120], 50))
(9, [1, 2])
(220, [1, 2])
Items 1 and 2 (0-based) are B and C. Time and memory are O(n · W).
3. One array instead of a table
Row i uses only row i − 1, so one array is enough — if you loop the capacity from high to low:
def knapsack_1d(wt, val, W):
dp = [0] * (W + 1)
for w, v in zip(wt, val):
for c in range(W, w - 1, -1): # high to low!
dp[c] = max(dp[c], v + dp[c - w])
return dp[W]
def wrong_direction(wt, val, W):
dp = [0] * (W + 1)
for w, v in zip(wt, val):
for c in range(w, W + 1): # low to high
dp[c] = max(dp[c], v + dp[c - w])
return dp[W]
print(knapsack_1d([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(wrong_direction([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(knapsack_1d([3], [10], 9), wrong_direction([3], [10], 9))
9
9
10 30
Why the direction matters. When we update dp[c], the value dp[c − w] must still be the old one (from the row above, "before this item"). Going high to low, dp[c − w] has a smaller index and has not been touched yet in this round. Going low to high, dp[c − w] was already updated with this item, so the item gets used again. The last line shows it clearly: one item of weight 3 and value 10, capacity 9. The correct answer is 10, but the low-to-high loop takes it three times and returns 30.
4. Unbounded knapsack
Sometimes each item can be used any number of times (a shop with unlimited stock, or coins). Then the "wrong" direction above is exactly right: loop the capacity low to high so an item can be reused in the same round. This is the same loop as coin change in the 1D DP lesson.
| Version | Each item | 1D capacity loop |
|---|---|---|
| 0/1 knapsack | at most once | high → low |
| Unbounded knapsack | any number of times | low → high |
5. Subset sum and equal partition
Subset sum: given numbers and a target, can some of them (each used at most once) add up to exactly target? It is a knapsack where the "value" is just yes/no.
- State:
can[t]= True if some subset seen so far sums tot. - Update for each number x:
can[t] = can[t] or can[t − x], withtgoing from high to low (each number used once). - Base:
can[0] = True(the empty subset).
Equal partition: can the numbers be split into two groups with the same sum? If the total is odd, no. Otherwise ask subset sum for total / 2 — if one group reaches half, the rest is the other half.
public class Main {
static boolean subsetSum(int[] nums, int target) {
boolean[] can = new boolean[target + 1];
can[0] = true;
for (int x : nums)
for (int t = target; t >= x; t--) // high to low: use x once
if (can[t - x]) can[t] = true;
return can[target];
}
static boolean canPartition(int[] nums) {
int total = 0;
for (int x : nums) total += x;
return total % 2 == 0 && subsetSum(nums, total / 2);
}
public static void main(String[] args) {
System.out.println(subsetSum(new int[]{2, 3, 7, 8}, 11));
System.out.println(subsetSum(new int[]{2, 4, 6}, 5));
System.out.println(canPartition(new int[]{1, 5, 11, 5}));
System.out.println(canPartition(new int[]{1, 2, 3, 5}));
}
}
true
false
true
false
{1, 5, 11, 5} splits into {11} and {1, 5, 5}. {1, 2, 3, 5} has total 11, which is odd, so it cannot be split.
To count the subsets instead of checking one exists, change or to + and start with count[0] = 1.
def count_subsets(nums, target):
count = [1] + [0] * target
for x in nums:
for t in range(target, x - 1, -1):
count[t] += count[t - x]
return count[target]
print(count_subsets([1, 2, 3, 4, 5], 5))
print(count_subsets([2, 3, 7, 8], 11))
3
1
Target 5 from 1..5 has three subsets: {5}, {1, 4} and {2, 3}.
6. How fast is it?
Knapsack runs in O(n · W), where W is the capacity number, not the input size. With 100 items and W = 1,000 that is only 100,000 steps. With W = 10⁹ the table cannot even be stored. Such an algorithm is called pseudo-polynomial: fast when the numbers are small, slow when they are huge. When a problem has a small n (about 20) but huge weights, try all subsets with bitmasks instead.
Common mistakes
- Using greedy by value per kg for 0/1 knapsack (it is correct only for the fractional version).
- Looping the capacity low to high in the 1D version of 0/1 knapsack, which lets an item be taken many times.
- Forgetting
can[0] = True(orcount[0] = 1); then nothing is ever reachable. - In equal partition, not checking for an odd total first.
- Trying to rebuild the chosen items from the 1D array — you need the full 2D table for that.
Quick recap
- 0/1 knapsack:
dp[i][c] = max(skip, v + dp[i − 1][c − w]); answer at the bottom-right. - Walk back from the corner to find the chosen items.
- 1D version: loop capacity high → low for 0/1, low → high for unbounded.
- Subset sum:
can[t] |= can[t − x]; equal partition = subset sum to half the total. - Time O(n · W), pseudo-polynomial; memory O(W) with one array.