Question Bank
Knapsack Family Quiz
Difficulty: Medium
0/1, unbounded, and bounded knapsack: state definitions, loop directions, and which variant fits a given problem.
Knapsack Family Quiz
0/1, unbounded, and bounded knapsack: state definitions, loop directions, and which variant fits a given problem.
189 views
3
Implement 0/1 knapsack with O(W) space. Inputs are item weights w, values v, and capacity W.
Examples
Example 1:
Input: w = [1, 3, 4, 5], v = [1, 4, 5, 7], W = 7
Output: 9
Explanation: Use a 1D dp[c] and iterate items outer, capacity inner from W down to w[i]. The reverse capacity loop ensures each item is considered at most once. Taking items at weights 3 and 4 gives value 4 + 5 = 9.Implement unbounded knapsack with O(W) space. Each item can be taken any number of times.
Examples
Example 1:
Input: w = [1, 3, 4], v = [10, 40, 50], W = 7
Output: 80
Explanation: Iterate capacity forward from w[i] up to W so dp[c - w[i]] may already include item i (allowing repeats). Optimal pack here is value 80 (e.g. weight 4 plus weight 3, or 7 copies of weight 1).Bounded knapsack lets you take item i up to count[i] times. Sketch the trick that turns it into 0/1 knapsack in O(W * sum(log count[i])).
You are told to partition an array into two subsets with equal sum. Which knapsack variant does this reduce to, and what is the target capacity?
Fix the bug in this 0/1 knapsack. It is overcounting items.
Examples
Example 1:
Input: w = [2, 3], v = [3, 4], W = 5
Output (buggy version): 9
Output (fixed version): 7
Explanation: The bug iterates capacity forward, so dp[c - w[i]] may already include item i. That allows taking the weight-2 item twice (value 3 + 3 + 4 = 10? actually capacity 5 only fits 2 + 3, so the overcount comes from re-entering an item). Reversing the loop to range(W, w[i] - 1, -1) restores 0/1 semantics.