The 0/1 knapsack
There are n items; item i weighs weights[i] and is worth
values[i]. Choose a set of items, each at most once, whose total weight is at most capacity, and
return the largest total value possible.
Examples
| Input | Output | Why |
|---|---|---|
weights = [1,3,4,5], values = [1,4,5,7], capacity = 7 | 9 | The 3 and the 4: weight 7, value 9. |
weights = [5,4,6,3], values = [10,40,30,50], capacity = 10 | 90 | Weights 4 and 3: value 90. |
weights = [10], values = [5], capacity = 9 | 0 | Nothing fits. |
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ weights[i] ≤ 1000
- 1 ≤ values[i] ≤ 10⁴
- 0 ≤ capacity ≤ 10⁴
Hints
Hint 1
Decide item by item. After the first i items, only the remaining capacity matters.
Hint 2
best[i][c] = max(best[i − 1][c], values[i] + best[i − 1][c − weights[i]]).
Hint 3
With one array, loop the capacity downwards so that best[c − w] still refers to the previous item.
Where people lose marks
- Looping capacities upwards with one array, which reuses items (that is the unbounded knapsack).
- Greedy by value per unit weight, which fails on the first example.
- Returning best[capacity] from a table initialised to −∞ instead of 0 for "exactly full".
Dry run on [1,3,4,5],[1,4,5,7],7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5
Base cases filled first.
-
Step 2 / 5
Row 1/1 filled.
-
Step 3 / 5
Row 3/4 filled.
-
Step 4 / 5
Row 4/5 filled.
-
Step 5 / 5
Row 5/7 filled. The answer is 9.
How to think about it
The state is (items considered, capacity): best[i][c] is the most value from the first i items within
capacity c. Item i is either skipped (best[i − 1][c]) or taken if it fits
(values[i] + best[i − 1][c − weights[i]]). Row i reads only row i − 1, so one array updated with capacities
going downwards does the job: the cells it reads have not been updated for this item yet.
Complexity. Time O(n · capacity) · Space O(capacity)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def knapsack_01(weights, values, capacity):
best = [0] * (capacity + 1) # best[c]: most value within capacity c
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # downwards: each item at most once
best[c] = max(best[c], v + best[c - w])
return best[capacity]#include <algorithm>
#include <vector>
long long solve(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
std::vector<long long> best(capacity + 1, 0);
for (size_t i = 0; i < weights.size(); ++i)
for (int c = capacity; c >= weights[i]; --c) // downwards: each item once
best[c] = std::max(best[c], values[i] + best[c - weights[i]]);
return best[capacity];
}class Solution {
public long knapsack01(int[] weights, int[] values, int capacity) {
long[] best = new long[capacity + 1];
for (int i = 0; i < weights.length; i++)
for (int c = capacity; c >= weights[i]; c--) // downwards: each item once
best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
return best[capacity];
}
}function knapsack01(weights, values, capacity) {
const best = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++)
for (let c = capacity; c >= weights[i]; c--) // downwards: each item once
best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
return best[capacity];
}fn solve(weights: &[i64], values: &[i64], capacity: i64) -> i64 {
let cap = capacity as usize;
let mut best = vec![0i64; cap + 1];
for (&w, &v) in weights.iter().zip(values) {
let w = w as usize;
for c in (w..=cap).rev() { // downwards: each item once
best[c] = best[c].max(v + best[c - w]);
}
}
best[cap]
}solve :: [Int] -> [Int] -> Int -> Int
solve weights values capacity = last (foldl addItem (replicate (capacity + 1) 0) (zip weights values))
where
-- the new row from the previous one: skip the item, or take it from capacity c - w of the previous row
addItem best (w, v) = [if c >= w then max b (v + best !! (c - w)) else b | (c, b) <- zip [0 ..] best]Variants to try
- The bag must be filled exactly: initialise best[0] = 0 and every other capacity to −∞.
- Return which items were taken (keep the 2-D table and walk back).
- Capacity up to 10⁹ but values small: index by total value and store the minimum weight.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.