80. 0/1 Knapsack · DSA Practice

Item i has weight weights[i] and value values[i]. Each item can be taken at most once. Return the maximum total value that fits in a bag of the given capacity. This classic problem is the basis of many interview questions (subset sum, partition, target sum).

Example 1

Input: weights = [1,3,4,5], values = [1,4,5,7], capacity = 7

Output: 9

Explanation: Take the items of weight 3 and 4: value 4 + 5 = 9.

Example 2

Input: weights = [5,4,6,3], values = [10,40,30,50], capacity = 10

Output: 90

Explanation: Weights 4 + 3: value 40 + 50.

Hint 1

dp[i][c] = max(skip item i, take item i if it fits).

Hint 2

With a 1-D array, loop capacity downwards so an item is not reused.

Dynamic ProgrammingKnapsack

Approach 1: Recursion

Take or skip each item.

⏱ Time O(2ⁿ)💾 Space O(n)

Approach 2: 2-D table

dp[i][c] over items and capacities.

⏱ Time O(n · W)💾 Space O(n · W)

Approach 3: 1-D array ✅

Reverse capacity loop.

⏱ Time O(n · W)💾 Space O(W)

Reference solution for 1-D array (time O(n · W), space O(W)). Each solution passes every test in all four languages.

class Solution:
    def knapsack(self, weights: List[int], values: List[int], capacity: int) -> int:
        dp = [0] * (capacity + 1)              # dp[c] = best value with capacity c
        for w, v in zip(weights, values):
            for c in range(capacity, w - 1, -1):   # backwards so each item is used once
                dp[c] = max(dp[c], dp[c - w] + v)
        return dp[capacity]

class Solution {
    public int knapsack(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];          // dp[c] = best value with capacity c
        for (int i = 0; i < weights.length; i++)
            for (int c = capacity; c >= weights[i]; c--)   // backwards: item used once
                dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
        return dp[capacity];
    }
}

class Solution {
public:
    int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
        vector<int> dp(capacity + 1, 0);           // dp[c] = best value with capacity c
        for (size_t i = 0; i < weights.size(); i++)
            for (int c = capacity; c >= weights[i]; c--)   // backwards: item used once
                dp[c] = max(dp[c], dp[c - weights[i]] + values[i]);
        return dp[capacity];
    }
};

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0); // dp[c] = best value with capacity c
  for (let i = 0; i < weights.length; i++)
    for (let c = capacity; c >= weights[i]; c--) // backwards: item used once
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
  return dp[capacity];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (2-D).