0/1 Knapsack and Subset Sum
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)You have a bag with a limit and a list of items. Each item is taken once or left. A table of best values for each number of items and each capacity answers it, and one row is enough.
Take it or leave it
The 0/1 knapsack problem picks items, each at most once, to get the highest total value without the total weight passing a limit. The 0 means left out and the 1 means taken.
A bag holds a fixed weight. Each item has a weight and a value, and goes in once or stays out. Trying every choice costs 2 to the power n. Each item has only two choices, and that is what the table will use.
weights = [3, 4, 5]values = [30, 50, 60]
def best(i, room): if i == len(weights) or room == 0: return 0 skip = best(i + 1, room) if weights[i] > room: return skip return max(skip, values[i] + best(i + 1, room - weights[i]))
print(best(0, 8))Example 1 · Brute force counts its calls
calls = 0
def best(i, room): global calls calls += 1 if i == 16 or room == 0: return 0 return max(best(i + 1, room), 1 + best(i + 1, room - 1))
print(best(0, 100), calls)16 131071
What this code does
- Sixteen items of weight 1 and value 1, with room for all of them.
- The calls double with every item: 131071 calls for 16 items. For 40 items this would never finish.
Each call either skips item i or takes it, so the calls form a tree with up to 2 to the power n leaves. The same (i, room) pair appears many times, and that is the repeated work.
The table: items by capacity
Let table[i][w] be the best value using only the first i items with room w. Item i stays out, giving table[i - 1][w], or goes in, giving its value plus table[i - 1][w minus its weight]. Take the larger.
def knapsack(weights, values, cap): n = len(weights) table = [[0] * (cap + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(cap + 1): table[i][w] = table[i - 1][w] if weights[i - 1] <= w: take = values[i - 1] + table[i - 1][w - weights[i - 1]] table[i][w] = max(table[i][w], take) return table[n][cap]Example 2 · The table, row by row
weights = [3, 4, 5]values = [30, 50, 60]cap = 8table = [[0] * (cap + 1) for _ in range(len(weights) + 1)]for i in range(1, len(weights) + 1): for w in range(cap + 1): table[i][w] = table[i - 1][w] if weights[i - 1] <= w: take = values[i - 1] + table[i - 1][w - weights[i - 1]] table[i][w] = max(table[i][w], take)for row in table: print(row)[0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 30, 30, 30, 30, 30, 30] [0, 0, 0, 30, 50, 50, 50, 80, 80] [0, 0, 0, 30, 50, 60, 60, 80, 90]
What this code does
- Row 0 is all zeros: no items, no value. Row 3 is the final answer, and its last cell, 90, is the best value for capacity 8.
- In row 2, capacity 7 gives 80: the items of weight 3 and 4 fit together.
Example 3 · Which items were taken
weights = [3, 4, 5]values = [30, 50, 60]cap = 8table = [[0] * (cap + 1) for _ in range(len(weights) + 1)]for i in range(1, len(weights) + 1): for w in range(cap + 1): table[i][w] = table[i - 1][w] if weights[i - 1] <= w: take = values[i - 1] + table[i - 1][w - weights[i - 1]] table[i][w] = max(table[i][w], take)chosen = []w = capfor i in range(len(weights), 0, -1): if table[i][w] != table[i - 1][w]: chosen.append(i - 1) w -= weights[i - 1]print(sorted(chosen), table[-1][cap])[0, 2] 90
What this code does
- Walk back from the last row. If the value changed from the row above, item i was taken, so remove its weight from the room.
- Items 0 and 2 (weights 3 and 5) give 30 + 60 = 90.
There are (n + 1) x (cap + 1) cells and each takes constant time. The cost is O(n x cap) time and space. Note that cap is a number, not a count of items.
Subset sum: can we hit the total exactly?
Same idea with yes or no answers. ok[i][s] is True when some of the first i numbers add up to s. Using no numbers makes sum 0 possible. A number x either stays out or adds x to a sum that was possible before.
def can_make(nums, target): n = len(nums) ok = [[False] * (target + 1) for _ in range(n + 1)] for i in range(n + 1): ok[i][0] = True for i in range(1, n + 1): for s in range(1, target + 1): ok[i][s] = ok[i - 1][s] if nums[i - 1] <= s and ok[i - 1][s - nums[i - 1]]: ok[i][s] = True return ok[n][target]Example 4 · Subset sum
def can_make(nums, target): n = len(nums) ok = [[False] * (target + 1) for _ in range(n + 1)] for i in range(n + 1): ok[i][0] = True for i in range(1, n + 1): for s in range(1, target + 1): ok[i][s] = ok[i - 1][s] if nums[i - 1] <= s and ok[i - 1][s - nums[i - 1]]: ok[i][s] = True return ok[n][target]
nums = [3, 34, 4, 12, 5, 2]print(can_make(nums, 9), can_make(nums, 30))True False
What this code does
- 9 is possible as 4 + 5. 30 is not, because 34 is too big and the rest add up to 26.
- The table answers every target up to 30 at once in its last row.
Example 5 · Split into two equal halves
def can_split(nums): total = sum(nums) if total % 2: return False reach = [False] * (total // 2 + 1) reach[0] = True for x in nums: for s in range(total // 2, x - 1, -1): if reach[s - x]: reach[s] = True return reach[total // 2]
print(can_split([1, 5, 11, 5]), can_split([1, 2, 3, 5]))True False
What this code does
- If the total is odd, two equal halves are impossible. Otherwise we need a subset that reaches half.
- 1 + 5 + 5 = 11 is half of 22, so the first list splits. The second totals 11, which is odd.
This is knapsack where weight and value are the same number and we only ask whether the total can be reached. It also costs O(n x target).
Save space: one row, filled right to left
Row i reads only row i - 1. Keep one list and update it from the largest capacity down to the smallest. A smaller capacity has not been updated yet, so it still holds the old row and each item is used once.
def knapsack_row(weights, values, cap): best = [0] * (cap + 1) for wt, val in zip(weights, values): for w in range(cap, wt - 1, -1): best[w] = max(best[w], val + best[w - wt]) return best[cap]Example 6 · Knapsack with one row
def knapsack_row(weights, values, cap): best = [0] * (cap + 1) for wt, val in zip(weights, values): for w in range(cap, wt - 1, -1): best[w] = max(best[w], val + best[w - wt]) return best[cap]
print(knapsack_row([3, 4, 5], [30, 50, 60], 8))90
What this code does
- It gives the same 90 as the full table, with one list of 9 numbers instead of 4 rows.
zipwalks weights and values together, which reads better than indexes.
Example 7 · The direction bug
def wrong(weights, values, cap): best = [0] * (cap + 1) for wt, val in zip(weights, values): for w in range(wt, cap + 1): best[w] = max(best[w], val + best[w - wt]) return best[cap]
print(wrong([3], [30], 9), wrong([3], [30], 2))90 0
What this code does
- One item of weight 3 and value 30 should give 30 at most. The left-to-right loop gives 90, because best[w - 3] already includes the item.
- That version solves a different problem, where an item may be taken any number of times.
Example 8 · Python shortcut: sums as bits of one integer
nums = [3, 34, 4, 12, 5, 2]sums = 1for x in nums: sums |= sums << xprint((sums >> 9) & 1, (sums >> 30) & 1)1 0
What this code does
- Bit s of
sumsis 1 when sum s can be made. Shifting left by x adds x to every sum at once. - Python integers have no size limit, so this works for large targets. An interviewer may still want the table, so know both.
Space drops from O(n x cap) to O(cap) and the time stays O(n x cap). Looping left to right would read values already updated for this item and use it many times.
Next step
Check your understanding
11 quick questions