0-1 Knapsack Problem

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}