0/1 Knapsack
DSA · Dynamic Programming
Theory
In the 0/1 knapsack problem each item has a weight and a value, and you must choose items (each at most once) to maximise total value without exceeding a weight capacity. The DP state dp[w] is the best value achievable with capacity w. For each item, iterate capacity from high to low and set dp[w] = max(dp[w], dp[w - weight] + value). It runs in O(n × W) time.
Why we use it
Knapsack is the template for many resource-allocation problems with limited budgets.
When to use it
Use it for budget allocation, choosing projects within a time limit, subset sum, partition equal subset sum and target-sum problems.
How it works
- dp[c] = 0 for all capacities
- For each item (weight w, value v)
- For c from capacity down to w
- dp[c] = max(dp[c], dp[c - w] + v)
- Return dp[capacity]
Syntax
dp = [0] * (W + 1)
for weight, value in items:
for w in range(W, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
Time: O(n·W) Space: O(W)Example
items = [("Laptop", 3, 60000), ("Camera", 2, 35000), ("Headphones", 1, 12000), ("Tablet", 2, 30000)]
capacity = 5
dp = [0] * (capacity + 1)
choice = [[] for _ in range(capacity + 1)]
for name, weight, value in items:
for w in range(capacity, weight - 1, -1):
if dp[w - weight] + value > dp[w]:
dp[w] = dp[w - weight] + value
choice[w] = choice[w - weight] + [name]
print("Best value:", dp[capacity])
print("Pack:", choice[capacity])Key points
- Each item used at most once
- Iterate capacity downwards
- O(n·W) time
- Template for subset-sum problems