背包问题

n个物品放入容积为w的背包中，如何放才能使背包中的物品价值最大，物品i对应的体积weights[i]，对应的价值为values[i]。

const knapsack = (n, w, weights, values, selected) => {
  if (n===0 || w ===0) {
    return 0;
  }

  for (let i = n - 1; i >= 0; i++) {
    if (weights[i] > w) {
        return knapsack(n - 1, w, weights, values, selected);
    }
    
    var a = knapsack(n - 1, w, weights, values, selected);
    var b = values[i] + knapsack(n - 1, weights[i], weights, values, selected);
    if (a > b) {
        selected[i] = 0;
        return a;
    } else {
        selected[i] = 1;
        return b;
    }
  }
}

var selected = [];
var weights = [2, 2, 6, 5, 4];
var values = [6, 3, 5, 4, 6];
var b = knapsack(5, 10, weights, values, selected);
console.log(b);