0/1 Knapsack
Hard · rating 1800 · dp
The first line contains n and capacity W. The second line contains n item weights. The third line contains n item values. Print the maximum total value that fits in capacity W; each item may be taken at most once.
Constraints: 1 ≤ n ≤ 100, 1 ≤ W ≤ 104
Editorial
The 0/1 Knapsack is a foundational dynamic-programming interview problem: maximise the total value packed into a bag of fixed capacity, taking each item at most once.
Approach
Let dp[w] be the best value for capacity w. Process items one at a time, iterating capacity downward: dp[w] = max(dp[w], dp[w - weight] + value).
dp = [0]*(W+1)
for wt, val in items:
for w in range(W, wt-1, -1):
dp[w] = max(dp[w], dp[w-wt] + val)
return dp[W]Why iterate downward
Going high-to-low guarantees dp[w-wt] still refers to a state without the current item — that's exactly what enforces the 0/1 (each item once) rule, versus the unbounded knapsack which iterates upward.
Complexity
Time: O(n × W). Space: O(W).