0/1 Knapsack

Medium
1600.

0/1 Knapsack

0/1 Knapsack is a medium coding problem on arrays and dynamic programming, asked in Amazon, Microsoft, Flipkart and Morgan Stanley interviews.

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 <= 1000
  • values.length == weights.length == n
  • 1 <= capacity <= 1000
  • 1 <= values[i], weights[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} capacity
 * @param {number[]} values
 * @param {number[]} weights
 * @return {number}
 */
var knapsack = function(capacity, values, weights) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • values.length == weights.length == n
  • 1 <= capacity <= 1000
  • 1 <= values[i], weights[i] <= 1000

Hints for 0/1 Knapsack

  1. Hint 1

    Greedy by value, by weight or by value-per-weight all fail on small examples — this needs dynamic programming.

  2. Hint 2

    Let best[c] be the most value achievable with total weight at most c using the items considered so far. How does adding one more item change it?

  3. Hint 3

    With one 1-D array, process capacities from capacity down 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

  1. Create best[0..capacity] filled with 0.
  2. For each item (v, w), loop c from capacity down to w and set best[c] = max(best[c], best[c - w] + v).
  3. 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 c upward 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 0 for 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