0-1 Knapsack Problem
Problem
n items each have a weight and a value, and the knapsack has capacity W. Take each item whole or not at all. Return the maximum total value whose total weight is at most W.
Example 1
Input: values = [60, 100, 120], weights = [10, 20, 30], W = 50 Output: 220
Items 2 and 3.
Also asked as: 0/1 knapsack · Knapsack Problem
Test cases
Case 1
Input: [10,20,30], [60,100,120], 50 Expected: 220
Case 2
Input: [1,2,3], [10,15,40], 6 Expected: 65
Case 3
Input: [4], [10], 3 Expected: 0
View solutionHide solution2 approaches
1. 2-D table
Time O(n · W)Space O(n · W)
dp[i][w] = best value using the first i items within weight w: skip item i, or take it if it fits.
function knapsack(weights, values, W) { const n = weights.length; const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0)); for (let i = 1; i <= n; i++) for (let w = 0; w <= W; w++) { dp[i][w] = dp[i - 1][w]; if (weights[i - 1] <= w) dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); } return dp[n][W];}2. 1-D rolling array
Time O(n · W)Space O(W)
Only the previous row is needed. Iterate w downward so each item is used at most once.
function knapsack(weights, values, W) { const dp = Array(W + 1).fill(0); for (let i = 0; i < weights.length; i++) for (let w = W; w >= weights[i]; w--) dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); return dp[W];}