中文
devexamples

Knapsack 01 Dynamic Programming Typed

Solve the 0-1 knapsack problem using typed dynamic programming with a rolling array for space optimization.

TypescriptData Integrity

Code

snippet
function knapsack01(weights: number[], values: number[], capacity: number): number {
  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