0-1 Knapsack (Dynamic Programming)
Problem
- Given
nitems, each with weightw[i]and valuev[i], and a knapsack capacityW, select a subset of items (each at most once) to maximize total value without exceeding capacity.
Key idea
- Use DP where
dp[i][c]is the maximum value achievable using the firstiitems with capacityc. The decision for itemiis to take it (if it fits) or skip it.
Recurrence
dp[0][*] = 0- For i from 1..n and capacity c from 0..W:
- if
w[i] > c:dp[i][c] = dp[i-1][c] - else:
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
- if
Space optimization
- You can reduce space to a 1D array
dp[c]iterating items and capacities in descending order (to avoid reuse within the same item).
Complexity
- Time: O(n * W)
- Space: O(n * W) or O(W) with the optimized 1D DP (but reconstructing chosen items needs extra bookkeeping).
Worked example
n = 4, W = 7
weights = [1,3,4,5]
values = [1,4,5,7]- Optimal: items with weights 3 and 4 (value 4 + 5 = 9) fit exactly into capacity 7.
Notes
- DP is pseudo-polynomial because it depends on
W. For largeWconsider approximation or meet-in-the-middle for moderaten.
Code: main.cpp — implements the DP and prints maximum value and chosen items.