中文
devexamples

Knapsack 01 Dynamic Programming (JavaScript)

Solve the 0-1 knapsack problem using dynamic programming with a one dimensional rolling array to reduce space complexity.

JavascriptData Integrity

Code

snippet
function knapsack01(weights, values, capacity) {
  const n = weights.length;
  let dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < n; i++) {
    const next = new Array(capacity + 1).fill(0);
    for (let w = 0; w <= capacity; w++) {
      next[w] = dp[w];
      if (w >= weights[i] && dp[w - weights[i]] + values[i] > next[w]) {
        next[w] = dp[w - weights[i]] + values[i];
      }
    }
    dp = next;
  }
  return dp[capacity];
}

Related Examples