0/1 KnapSack

Return maximum value a thief can steal with a given capacity

0-1 Knapsack Problem

Problem Statement

You are given two arrays, val and wt, which represent the values and weights of n items. You are also given an integer W, which is the maximum weight capacity of a knapsack (a bag).

Your goal is to find the maximum total value you can get by picking a subset of items.

• The total weight of the items you pick must not be greater than the capacity W.
• You can either pick a complete item or leave it behind. You cannot break an item into pieces (this is the 0-1 property).

Examples

Example 1

• Input: val = [60, 100, 120], wt = [10, 20, 30], W = 50
• Output: 220
• Explanation: Select the items with weights 20 and 30. Their total value is 100 + 120 = 220.

Example 2

• Input: val = [10, 40, 30, 50], wt = [5, 4, 6, 3], W = 10
• Output: 90
• Explanation: Select the items with weights 4 and 3. Their total value is 40 + 50 = 90.

Memoization (Top-Down Approach)

We look at each item starting from the last one and make a choice: pick it or do not pick it.

• If we pick the item, we add its value and reduce the knapsack's remaining capacity.
• If we do not pick the item, the capacity stays the same.
• We save our answers in a Map using a unique key (index#weight) so we never calculate the same sub-problem twice.

  knapsack01(wt, val, n, W) {
    let dp = new Map();
    
    function recurr(index, weight) {
      if (weight == 0) {
        return 0;
      }
      
      let key = `${index}#${weight}`;

      if (index == 0) {
        if (wt[0] <= weight) {
          return val[0];
        } else {
          return 0;
        }
      }

      if (dp.has(key)) {
        return dp.get(key);
      }

      let pick = 0;

      if (wt[index] <= weight) {
        pick = val[index] + recurr(index - 1, weight - wt[index]);
      }

      let notPick = recurr(index - 1, weight);

      let ans = Math.max(pick, notPick);

      dp.set(key, ans);
      return ans;
    }

    return recurr(n - 1, W);
  }

Tabulation (Bottom-Up Approach)

Instead of using recursion, we can build a 2D array (table) from the bottom up.

• The state dp[i][w] tells us the maximum value we can get using items up to index i with a weight limit w.
• Base Condition: For the first item (index = 0), we fill the array with its value for all weights from wt[0] up to the maximum capacity.

function knapsack(weights, values, n, maxWeight) {
  // Create the DP table
  let dp = Array.from({ length: n }, () => Array(maxWeight + 1).fill(0));

  // Base case: Fill the first row for the first item
  for (let w = weights[0]; w <= maxWeight; w++) {
    dp[0][w] = values[0];
  }

  // Fill the DP table
  for (let index = 1; index < n; index++) {
    for (let w = 0; w <= maxWeight; w++) {
      let notTake = dp[index - 1][w];
      let take = -Infinity;
      
      if (weights[index] <= w) {
        take = values[index] + dp[index - 1][w - weights[index]];
      }
      
      dp[index][w] = Math.max(notTake, take);
    }
  }

  return dp[n - 1][maxWeight];
}

Space Optimization

In the tabulation method, to calculate the current row (index), we only ever look at the previous row (index - 1).

• We can remove the 2D array and just use a single 1D array (prev) of size maxWeight + 1.
• Important trick: We must iterate through the weights backwards (from maxWeight down to 0). This prevents us from accidentally using an updated value from the current row instead of the previous row.

function knapsack(weights, values, n, maxWeight) {
  // Create a single array to store the maximum values
  let prev = new Array(maxWeight + 1).fill(0);

  // Base case: for the first item, fill the array
  for (let w = weights[0]; w <= maxWeight; w++) {
    prev[w] = values[0];
  }

  // Iterate through items
  for (let i = 1; i < n; i++) {
    // Iterate backwards to optimize space to O(W)
    for (let w = maxWeight; w >= 0; w--) {
      let notTake = prev[w];
      let take = -Infinity;
      
      if (weights[i] <= w) {
        take = values[i] + prev[w - weights[i]];
      }
      
      prev[w] = Math.max(notTake, take);
    }
  }
  
  return prev[maxWeight];
}