DSA course menu
The Knapsack Problem: 0/1 and Unbounded Knapsack in Python
Learn the 0/1 knapsack problem with dynamic programming: the DP table, choosing items, the one-row space optimisation, unbounded knapsack, subset sum and partition problems, and fractional knapsack with greedy.
On this page
You have a bag that holds a limited weight, and items with a weight and a value. Which items should you take to carry the most value? This is the knapsack problem. It models budgets, cargo loading, picking projects with limited time, and many interview questions in disguise.
In the 0/1 knapsack, each item is taken whole or not at all, at most once.
Why simpler ideas fail#
Trying every subset is O(2ⁿ). Greedy "best value per kilogram first" fails because a high-ratio item can waste space:
items = [("laptop", 3, 2000), ("camera", 2, 1500), ("watch", 2, 1400)] # name, kg, value
capacity = 5
by_ratio = sorted(items, key=lambda x: x[2] / x[1], reverse=True)
weight = value = 0
taken = []
for name, w, v in by_ratio:
if weight + w <= capacity:
weight += w
value += v
taken.append(name)
print("greedy by value per kg:", taken, value)greedy by value per kg: ['camera', 'watch'] 2900Greedy takes the camera (750 per kg) and the watch (700 per kg), using 4 kg, and then the laptop no longer fits. But laptop + camera weighs exactly 5 kg and is worth 3500. Dynamic programming finds that answer by checking every option systematically, without trying every subset.
The DP table#
- State:
dp[i][w]= the best value using only the firstiitems with capacityw. - Recurrence: for item i (weight
wi, valuevi), either skip it (dp[i-1][w]) or, if it fits, take it (dp[i-1][w - wi] + vi). Keep the larger. - Base: with no items, or capacity 0, the value is 0.
def knapsack(items, capacity):
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
name, wi, vi = items[i - 1]
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # skip
if wi <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi) # take
# walk back to find which items were taken
taken, w = [], capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
name, wi, vi = items[i - 1]
taken.append(name)
w -= wi
return dp[n][capacity], taken[::-1]
items = [("laptop", 3, 2000), ("camera", 2, 1500), ("watch", 2, 1400), ("book", 1, 300)]
for cap in [4, 5, 6]:
print(cap, knapsack(items, cap))4 (2900, ['camera', 'watch'])
5 (3500, ['laptop', 'camera'])
6 (3800, ['laptop', 'camera', 'book'])The cost is O(n × W) for n items and capacity W. That is called pseudo-polynomial: it is fast when W is small, but a capacity of a billion makes the table impossibly large.
One row is enough#
Each row only reads the row above. Using a single list and looping capacity downwards keeps each item from being used twice (the values to the left still belong to the previous row):
def knapsack_1d(items, capacity):
dp = [0] * (capacity + 1)
for _, wi, vi in items:
for w in range(capacity, wi - 1, -1): # downwards!
dp[w] = max(dp[w], dp[w - wi] + vi)
return dp[capacity]
items = [("laptop", 3, 2000), ("camera", 2, 1500), ("watch", 2, 1400), ("book", 1, 300)]
print(knapsack_1d(items, 5), knapsack_1d(items, 6))3500 3800Unbounded knapsack#
If every item can be taken any number of times, loop capacity upwards, so an item already taken at a smaller capacity can be taken again:
def unbounded_knapsack(items, capacity):
dp = [0] * (capacity + 1)
for _, wi, vi in items:
for w in range(wi, capacity + 1): # upwards: reuse allowed
dp[w] = max(dp[w], dp[w - wi] + vi)
return dp[capacity]
rods = [("1m", 1, 1), ("2m", 2, 5), ("3m", 3, 8), ("4m", 4, 9)]
print(unbounded_knapsack(rods, 8))21This is the rod cutting problem: cutting an 8 m rod into pieces with these prices earns 21 at best (2 m + 3 m + 3 m = 5 + 8 + 8). The only difference from 0/1 knapsack is the direction of the inner loop.
Subset sum and partition#
Can some of these numbers add up exactly to a target? It is a knapsack with "reachable or not" instead of values:
def subset_sum(nums, target):
reachable = [True] + [False] * target
for x in nums:
for t in range(target, x - 1, -1):
reachable[t] = reachable[t] or reachable[t - x]
return reachable[target]
def can_partition(nums): # split into two halves with equal sums
total = sum(nums)
return total % 2 == 0 and subset_sum(nums, total // 2)
print(subset_sum([3, 34, 4, 12, 5, 2], 9))
print(subset_sum([3, 34, 4, 12, 5, 2], 30))
print(can_partition([1, 5, 11, 5]), can_partition([1, 2, 3, 5]))True
False
True False[1, 5, 11, 5] splits into [11] and [1, 5, 5], both summing to 11.
Fractional knapsack: greedy works#
If items can be cut (grain, fuel, time), take items in order of value per kilogram and cut the last one to fill the bag exactly. Greedy is optimal here because no space is ever wasted:
def fractional_knapsack(items, capacity):
total = 0.0
for name, w, v in sorted(items, key=lambda x: x[2] / x[1], reverse=True):
take = min(w, capacity)
total += v * take / w
capacity -= take
if capacity == 0:
break
return total
print(fractional_knapsack([("rice", 10, 60), ("dal", 20, 100), ("sugar", 30, 120)], 50))240.0All the rice and dal (160) plus two thirds of the sugar (80): 240.
Common mistakes#
Practice#
Practice exercise
Target sum: put a + or - in front of every number so the expression equals target. Write count_signs(nums, target) that returns the number of ways.
Show hint
If P is the sum of the + numbers and N of the - numbers, then P − N = target and P + N = total, so P = (total + target) / 2. Count the subsets that sum to P (a counting version of subset sum, looping downwards).
Show solution
def count_signs(nums, target):
total = sum(nums)
if abs(target) > total or (total + target) % 2:
return 0
goal = (total + target) // 2
ways = [1] + [0] * goal
for x in nums:
for t in range(goal, x - 1, -1):
ways[t] += ways[t - x]
return ways[goal]
print(count_signs([1, 1, 1, 1, 1], 3))
print(count_signs([1], 2))5
0There are 5 ways for the first input: choose which single 1 gets the minus sign.
Key takeaway#
Next: putting it all together for interviews, in How to Solve Coding Problems.
Finished this lesson?