0/1 Knapsack DP DSA Solution

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.

0/1 Knapsack: Capacity DP Pattern