Medium · One-Dimensional Knapsack DP
Understand → Visualise → Practice.
Each item may be taken at most once. Return the maximum total value whose total weight does not exceed capacity.
dp[c] is the best value achievable with capacity c. For each item, update capacities from high to low, so the item is used at most once.
dp has capacity + 1 zeros: with no items every capacity is worth 0.
For room from capacity down to its weight, dp[room] = max(dp[room], dp[room − weight] + value).
After all items, dp[capacity] is the best total value.
O(items × capacity) time and O(capacity) space.
Forward capacity iteration changes 0/1 knapsack into unbounded knapsack.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.