Learning Outcome
After this lesson, you should be able to use capacity states and update backward so each item is used at most once.
Problem Statement
Given item weights, item values, and capacity, return the maximum value that fits in the bag when each item can be used once.
| Input | Output | Why |
|---|---|---|
weights = [1,3,4], values = [15,20,30], capacity = 4 | 35 | Take weight 1 value 15 and weight 3 value 20. |
Brute Force Approach
Try every subset of items and compute total weight and value. This is exponential.
Optimized Approach
Use 1D DP over capacities. For each item, update capacities backward so the same item cannot be reused in the same round.
Exact Pseudocode
dp[0..capacity] = 0
for each item i:
for cap from capacity down to weights[i]:
dp[cap] = max(dp[cap], dp[cap - weights[i]] + values[i])
return dp[capacity]Reference Code
class Solution:
def knapSack(self, capacity, weights, values):
dp = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for cap in range(capacity, weight - 1, -1):
dp[cap] = max(dp[cap], dp[cap - weight] + value)
return dp[capacity]Sample Dry Run
| Step | State | Result |
|---|---|---|
| Item weight 1 value 15 | Fill capacities 1..4 | best at cap 4 is 15 |
| Item weight 3 value 20 | cap 4 can use dp[1] + 20 | best at cap 4 is 35 |
| Item weight 4 value 30 | cap 4 compares 35 vs 30 | keep 35 |
| Return | dp[4] | answer = 35 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(items * capacity) | Each item updates each capacity once. |
| Space | O(capacity) | The dp array stores best value for each capacity. |
Edge Cases
- Capacity 0 should return 0.
- Items heavier than capacity are skipped naturally.
- Backward capacity loop is required for 0/1 usage.
Interview Checklist
- Loop capacity backward for 0/1 knapsack.
- Looping forward turns it into unbounded knapsack.
- Use value, not weight, as the maximized score.
FAQs
Why update capacities backward?
Backward updates prevent the current item from being used more than once in the same item round.
How is this different from unbounded knapsack?
Unbounded knapsack allows reusing an item, so it usually loops capacity forward.
What is the core pattern?
Capacity DP.