fixed bug

01knapsack.js

const knapsack = (vals, weights, limit, memo = new Map()) => {
  // sub problems are going to be whether we take something or 
  if (vals.length === 0) return 0;
  if (memo.has(`${vals}${weights}`)) return memo.get(`${vals}${weights}`);
  const currentWeight = weights[0];
  const currentVal = vals[0];
  const leftOverWeight = limit - currentWeight;
  // if we cant take first item
  if (leftOverWeight < 0) return knapsack(vals.slice(1), weights.slice(1), limit, memo);
  // first call is we dont take it, second we do
  // regardless of taking it, both arrays get sliced
  // if we do, limit gets lowered
  memo.set(`${vals}${weights}`, Math.max(knapsack(vals.slice(1), weights.slice(1), limit, memo), 
  currentVal + knapsack(vals.slice(1), weights.slice(1), leftOverWeight, memo)));
  return memo.get(`${vals}${weights}`);
};
// recursive 0/1 knapsack
// memoization does not help much
// tabulation is definitely faster
console.log(knapsack([1, 2, 5, 9], [1, 4, 4, 10], 9)); // 8