背包问题 JS 实现

物品列表 [[重量, 价值], ...]，背包承重 10，求最大价值：

var items = [
  [2, 5],
  [3, 1],
  [5, 4],
  [6, 10],
];

function knapsack(capacity, items) {
  var res = [];
  for (var i = 0; i <= capacity; i++) res[i] = 0;
  for (var i = 0; i < items.length; i++) {
    for (var j = capacity; j > items[i][0]; j--) {
      res[j] = Math.max(res[j], res[j - items[i][0]] + items[i][1]);
    }
  }
  return res[capacity];
}

knapsack(10, items); // 15