Pattern Recognition Drill
Medium Dynamic Programming
The Problem
Maximize value in a knapsack of capacity W, each item used at most once.
What approach would you use?
Think about it before scrolling down.
dp[i][w] = max value with first i items and capacity w. Include or exclude each item. O(n*W).
Common Trap
Greedy (best value/weight ratio) doesn't work for 0/1 knapsack. DP is required.