Knapsack
O(nW) SpaceO(nW) Imagine packing for a hiking trip with a weight limit. Each item has a weight and a value (usefulness). You can’t take everything, so you need to pick the combination that maximizes total usefulness without exceeding the weight limit. You consider each item: take it or leave it?
When to use it: Optimization problems with a capacity constraint — budget allocation, subset selection with a target sum, resource scheduling. The 0/1 knapsack is the foundation of many DP problems.
Key insight: For each item, you have two choices: include it (add its value, reduce remaining capacity) or skip it (keep current capacity). Build a table where dp[i][w] is the best value using the first i items with capacity w.
Common trap: Confusing 0/1 knapsack (each item used at most once) with unbounded knapsack (items can be reused). The iteration order of the 1D optimization differs between the two.
# 0/1 Knapsack: each item can be used at most once
function knapsack(weights, values, capacity):
n = length(weights)
dp = 2D array of size (n + 1) x (capacity + 1), initialized to 0
for i = 1 to n:
for w = 0 to capacity:
dp[i][w] = dp[i-1][w] # skip item i
if weights[i-1] <= w:
# take item i if it improves value
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Space-optimized 1D version
function knapsack1D(weights, values, capacity):
dp = array of size (capacity + 1), initialized to 0
for i = 0 to n - 1:
for w = capacity down to weights[i]: # reverse order for 0/1
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
"""0/1 Knapsack: maximize value within weight capacity."""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # skip item
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
def knapsack_01_optimized(weights: list[int], values: list[int], capacity: int) -> int:
"""Space-optimized 0/1 Knapsack using 1D array."""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1): # reverse for 0/1
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def unbounded_knapsack(weights: list[int], values: list[int], capacity: int) -> int:
"""Unbounded Knapsack: each item can be used unlimited times."""
dp = [0] * (capacity + 1)
for w in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def subset_sum(nums: list[int], target: int) -> bool:
"""Can a subset of nums sum to exactly target? (Knapsack variant.)"""
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for t in range(target, num - 1, -1):
dp[t] = dp[t] or dp[t - num]
return dp[target]Problem: Given a set of positive integers and a target sum, determine if there exists a subset that sums to exactly the target.
How would you approach this?
Answer: This is the subset sum problem, a variant of 0/1 knapsack. Each number is an "item" with weight = value = its magnitude. Use a boolean DP array where dp[t] means "can we make sum t?" Iterate numbers in reverse to ensure each is used at most once.
Problem: A thief can carry at most W kg. There are n items, each with a weight and a dollar value. Maximize the total value without exceeding the weight limit. Each item can only be taken once.
How would you approach this?
Answer: This is the classic 0/1 knapsack. Build dp[i][w] = max value using items 1..i with capacity w. For each item, choose the better of skipping it or taking it (if it fits). Optimize to 1D by iterating capacity in reverse.
Time: O(nW) where n is the number of items and W is the capacity. We fill an n x W table, with O(1) work per cell. Note: this is pseudo-polynomial — polynomial in the numeric value of W, not in the number of bits to represent it.
Space: O(nW) for the 2D table. Can be optimized to O(W) using a 1D array, since each row only depends on the previous row.