0/1 Knapsack — Solution in Python, Java & C++
0/1 Knapsack solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
0/1 Knapsack is a medium coding problem on arrays and dynamic programming, asked in Amazon, Microsoft, Flipkart and Morgan Stanley interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft, Flipkart, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a knapsack that can carry a total weight of at most capacity, and n items. Item i is worth values[i] and weighs weights[i].
Each item is either taken whole or left behind — you cannot take a fraction of an item, and you cannot take the same item twice (hence 0/1).
Return the maximum total value of a selection of items whose total weight does not exceed capacity. If no item fits, the answer is 0.
Example 1
Input: capacity = 4, values = [1,2,3], weights = [4,5,1]
Output: 3
Explanation: Item 1 (weight 5) never fits, and items 0 and 2 together weigh 5. The best single choice is item 2, worth 3.
Example 2
Input: capacity = 50, values = [60,100,120], weights = [10,20,30]
Output: 220
Explanation: Take the items weighing 20 and 30: total weight 50, total value 100 + 120.
Example 3
Input: capacity = 3, values = [1,2,3], weights = [4,5,6]
Output: 0
Explanation: Every item is heavier than the knapsack.
Constraints
1 <= n <= 1000values.length == weights.length == n1 <= capacity <= 10001 <= values[i], weights[i] <= 1000
Hints for 0/1 Knapsack
Hint 1
Greedy by value, by weight or by value-per-weight all fail on small examples — this needs dynamic programming.
Hint 2
Let
best[c]be the most value achievable with total weight at mostcusing the items considered so far. How does adding one more item change it?Hint 3
With one 1-D array, process capacities from
capacitydown to the item's weight:best[c] = max(best[c], best[c - w] + v). Going downwards keeps each item from being used twice.
How to solve 0/1 Knapsack
Decide the items one at a time. After the first i items, best[c] is the largest value packable into weight c; item i either stays out (value unchanged) or goes in on top of the best packing of the remaining c - w capacity.
Approach
- Create
best[0..capacity]filled with0. - For each item
(v, w), loopcfromcapacitydown towand setbest[c] = max(best[c], best[c - w] + v). - Return
best[capacity].
Why it works
Any optimal packing for capacity c among the first i items either excludes item i — then it is an optimal packing of the first i - 1 items — or includes it, and then the rest is an optimal packing of the first i - 1 items into c - w. Iterating c downward means best[c - w] still holds the value from before item i was considered, which is exactly that sub-problem, so no item is counted twice.
Complexity
- Time —
O(n * capacity) - Space —
O(capacity)
Pitfalls
- Looping
cupward turns this into the unbounded knapsack (an item could be reused). - Value-per-weight greedy is only correct for the fractional knapsack.
- The array must start at
0for every capacity, not at-infinity— the knapsack need not be full.
Reference solution
Python
from typing import List
def knapsack(capacity: int, values: List[int], weights: List[int]) -> int:
best = [0] * (capacity + 1)
for v, w in zip(values, weights):
for c in range(capacity, w - 1, -1):
cand = best[c - w] + v
if cand > best[c]:
best[c] = cand
return best[capacity]Java
public static int knapsack(int capacity, int[] values, int[] weights) {
int[] best = new int[capacity + 1];
for (int i = 0; i < values.length; i++) {
int v = values[i], w = weights[i];
for (int c = capacity; c >= w; c--) {
best[c] = Math.max(best[c], best[c - w] + v);
}
}
return best[capacity];
}C++
int knapsack(int capacity, vector<int>& values, vector<int>& weights) {
vector<int> best(capacity + 1, 0);
for (size_t i = 0; i < values.size(); i++) {
int v = values[i], w = weights[i];
for (int c = capacity; c >= w; c--) best[c] = max(best[c], best[c - w] + v);
}
return best[capacity];
}JavaScript
var knapsack = function(capacity, values, weights) {
var best = new Array(capacity + 1).fill(0);
for (var i = 0; i < values.length; i++) {
var v = values[i], w = weights[i];
for (var c = capacity; c >= w; c--) {
if (best[c - w] + v > best[c]) best[c] = best[c - w] + v;
}
}
return best[capacity];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming