0/1 knapsack DP
- Algorithms course
- Advanced
- Lesson 14/56
- 4 min
Build a DP table for 0/1 knapsack.
0/1 knapsack DP
We build a 2D DP table for 0/1 knapsack. dp[i][w] is the max value using the first i items with capacity w.
The table is (n+1) × (W+1); the first row and column are zero.
Each cell stores the best of take-or-skip for that item.
Cell recurrence
If weights[i-1] ≤ w then dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]]). Else dp[i][w] = dp[i-1][w].
This recurrence clearly encodes the take-or-skip decision for each item.
The result is in dp[n][W]; the bottom-right corner of the table.
Practice Knapsack DP
Write knap_dp(W, weights, values, n). 0/1 knapsack with a 2D DP table. Print 220 with print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3)).
Starter code
def knap_dp(W, weights, values, n):
# Knapsack DPSample solution
def knap_dp(W, weights, values, n):
# Knapsack DP
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
print(knap_dp(50, [10, 20, 30], [60, 100, 120], 3))Expected output
220
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Take recurrence
take = values[i - 1] + dp[____][w - weights[i - 1]]take = values[i - 1] + dp[i - 1][w - weights[i - 1]]Explanation: i - 1 is right.
2 0/1 knapsack DP: match the terms
| Term | Meaning |
|---|---|
dp[i][w] |
Cell |
take |
Take |
skip |
Skip |
max |
Max |
3 What is 0/1 knapsack DP's time complexity?
- O(n^2)
- O(nW) Correct answer
- O(W^2)
- O(n + W)
Explanation: O(nW).