0/1 Knapsack Problem: How Would You Solve It?
Learn how to solve the 0/1 knapsack problem with dynamic programming, the recurrence, complexity, and a Python implementation.
Expected Interview Answer
The 0/1 knapsack problem is solved with dynamic programming: build a table dp[i][w] representing the best value achievable using the first i items within capacity w, where each item is either fully included or fully excluded, never split.
For each item you decide, at every capacity, whether taking it (if it fits) beats leaving it out: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) when weight[i] <= w, else dp[i][w] = dp[i-1][w]. This runs in O(n*W) time and space, where n is the item count and W is the capacity, which is pseudo-polynomial since it depends on the numeric value of W, not just its bit length. Because each item's decision only depends on the previous row, the table can be compressed to a single 1D array of size W+1 iterated from high capacity to low, cutting space to O(W). The 0/1 constraint is what makes this fundamentally different from fractional knapsack, which is solved greedily instead.
- Optimal value guaranteed via exhaustive but memoized choices
- O(n*W) time, reducible to O(W) space with a 1D array
- Reconstructing the chosen items is straightforward from the table
- Template generalizes to many subset-selection DP problems
AI Mentor Explanation
A team selector filling a fixed number of overs has to decide, bowler by bowler, whether including a bowler's full spell is worth the overs it costs, since a bowler cannot be used for half a spell. For each bowler considered, the selector compares the best outcome from skipping them against the best outcome from using their full spell plus whatever remaining overs allow from bowlers already evaluated. This bowler-by-bowler, overs-by-overs table of best outcomes is exactly the knapsack DP table. Once filled, tracing back through the table reveals exactly which bowlers were selected to maximize overall impact within the fixed over limit.
Step-by-Step Explanation
Step 1
Define the state
dp[i][w] = max value achievable using the first i items within capacity w.
Step 2
Write the recurrence
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w, else dp[i-1][w].
Step 3
Fill the table bottom-up
Iterate items outer, capacities inner (or compress to a 1D array iterated capacity high-to-low).
Step 4
Reconstruct if needed
Trace back through dp to find which items were included by comparing dp[i][w] against dp[i-1][w].
What Interviewer Expects
- State the DP recurrence correctly, including the "don't take" branch
- Explain why greedy fails here but works for fractional knapsack
- Give the O(n*W) time/space and mention the 1D space optimization
- Explain why iterating capacity high-to-low is required in the 1D version
Common Mistakes
- Iterating the 1D array low-to-high, causing items to be reused (turns it into unbounded knapsack)
- Forgetting the base case dp[0][w] = 0 for all w
- Confusing 0/1 knapsack with fractional knapsack and reaching for a greedy solution
- Not checking weight[i] <= w before considering the "take" branch
Best Answer (HR Friendly)
“0/1 knapsack is about picking a subset of items to maximize value without exceeding a weight limit, where each item is all-or-nothing. I solve it by building a table that tracks the best value possible for every combination of items considered so far and every possible remaining capacity, and I can shrink that table down to a single row for less memory.”
Code Example
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for cap in range(capacity, w - 1, -1):
dp[cap] = max(dp[cap], v + dp[cap - w])
return dp[capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_01(weights, values, 5)) # 7 (items of weight 2 and 3)Follow-up Questions
- How would you reconstruct which items were chosen, not just the max value?
- How does this differ from the unbounded knapsack problem?
- Why does iterating capacity in reverse matter for the 1D array?
- How would you handle a knapsack with two constraints, like weight and volume?
MCQ Practice
1. In the 1D space-optimized 0/1 knapsack, why must the capacity loop go from high to low?
Iterating high-to-low ensures dp[cap - w] still reflects values from before the current item was considered, avoiding reuse.
2. What is the time complexity of the standard 0/1 knapsack DP solution?
The table has n rows and W+1 columns, each filled in O(1), giving O(n * W) time.
3. Why can 0/1 knapsack not be solved with a simple greedy strategy the way fractional knapsack can?
Because items are all-or-nothing, taking the highest value-per-weight item first can leave capacity that no other item combination uses well, unlike the fractional version.
Flash Cards
What is the 0/1 knapsack DP recurrence? — dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if it fits, else dp[i-1][w].
What is the time complexity? — O(n * W), pseudo-polynomial since it depends on the numeric capacity W.
Why iterate capacity high-to-low in the 1D version? — To avoid reusing the same item multiple times within one pass.
How does 0/1 differ from fractional knapsack? — 0/1 items are all-or-nothing (needs DP); fractional items can be split (solved greedily).