You are given n items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its capacity. You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacit…

zero-one-knapsack.js

export function findMaxKnapsackProfit(capacity, weights, values) {
  // a single array version,
  // it's an optimized two-array version (repeatedly swap two arrays to hold previous and current row)
  // which is in itself an optimized 2d array solution
  const dp = Array(capacity + 1).fill(0);

  // first we build an array of solutions for each possible capacity with only the first item considered
  // then we update the array by considering the second item
  // after that array contains optimal solutions with both items considered, so we can move to third, and so on
  for (let item = 0; item < weights.length; ++item) {
    const weight = weights[item];
    const value = values[item];
    // iterate capacities in reverse, because
    // imagine we are at item C, and we previously iterated on some item A and B
    // we are considering the item C with weight 2 to a capacity of 6,
    // it means we need to get access to the optimal solution
    // at capacity 4 (6-2) of the previous iteration (with optimal solutions with two other items)
    // if we iterate capacities normally,
    // the solution at capacity 4 will already be overwritten by the time we reach capacity 6
    for (let cap = capacity; cap > 0; --cap) {
      if (weight > cap) {
        // since we are iterating in reverse,
        // if item cannot fit capacity, we know for sure it wont fit any subsequent capacities
        break;
      }
      // calculate solution when including this item into the current capacity
      // we need to sum the item value + the optimal solution for the remainder of capacity
      // (which we already have calculated when we were considering the previous items)
      const includingValue = value + dp[cap - weight];
      // calculate solution when excluding this item
      // just take the current value since it's still there from the previous iteration
      const excludingValue = dp[cap];
      // write the solution by taking the max
      dp[cap] = Math.max(includingValue, excludingValue);
    }
  }
  // the last element is the solution of the problem when considering all items at max capacity
  return dp[dp.length - 1];
}

// tc: O(n*c) where n is the number of items, and c is capacity
// sc: O(c)