0/1 Knapsack Problem

1// 1D Array Space-Optimized 0/1 Knapsack: O(N * W) Time, O(W) Space
2function knapsack(weights, values, W) {
3  const n = weights.length;
4  // dp[w] stores maximum value achievable with capacity w
5  const dp = new Array(W + 1).fill(0);
6 
7  for (let i = 0; i < n; i++) {
8    const wt = weights[i];
9    const val = values[i];
10 
11    // Traverse backwards from W down to wt so each item is picked AT MOST ONCE
12    for (let w = W; w >= wt; w--) {
13      dp[w] = Math.max(dp[w], val + dp[w - wt]);
14    }
15  }
16 
17  return dp[W];
18}
19 
20// Example usage:
21// const weights = [1, 2, 3];
22// const values = [10, 15, 40];
23// const W = 6;
24// knapsack(weights, values, W); // Returns 65 (Items with wt 1, 2, 3 => 10 + 15 + 40)