动态规划——0-1背包问题（JavaScript解法）

背包问题是一个组合优化问题，题目描述如下：
给定一个固定大小、容量为C的背包，以及一组有价值和重量的物品，找出一个最佳的解决方案，使得装入背包的物品重量小于W，且价值最大。
通俗的描述就是：
你有一个书包，还有一堆物品摆在你的面前，手机、电脑、平板、砖头，而你的书包只能装5斤东西，装哪些东西最赚？

理解了题目意思我们再来看一个输入输出例子

输入

weight:[2,3,4,5,9] //重量
values:[3,4,5,8,10] //价值
C:20 //背包容量

物品	价值	重量
0	3	2
1	4	3
2	5	4
3	8	5
4	10	9

输出

选取物品0、2、3、4，总价值为3+5+8+10 = 26

maxValue:26

我们假设公式B(k,c)表示有k个物品，容量为C时的最大价值
问题便转为求B(4,20)的值

1. 当k指向第4个物品时，重量为9，明显小于背包容量C，所以我们可以将物品4装入背包，故
   B(4,20) = B(3,20-9)+10 = B(3,11)+10

别忘了我们追求的是最大价值，如果把物品4装进去那容量就变小了，装不进其他物品，所以对于小于背包容量的物品，我们有两个选择

• 装进去
  B(4,20) = B(3,20-9)+10 = B(3,11)+10
• 不装
  B(4,20) = B(3,20)

如果物品4的重量为100，明显超出背包容量时，那B(4,20)等于多少呢？
既然装不下，那我们就忽略掉物品4，让k指针指向上一个物品，容量不变
B(4,20) = B(3,20)

通过以上分析我们可以得出B(k,c)的递归公式

我们来分析B(4,20)的执行过程，可以发现实际上这个公式是二叉树的形式

看懂了上图，这题可以使用递归方法解决，但更好地解法是使用动态规划。
动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术

算法如下：

function kanpSack(capacity, weights, values, n) {
  var a,b,KS = []
   
//首先，初始化用于寻找解决方案的矩阵KS[n+1][capacity+1]
  for (var i = 0; i <= n; i++) {
    KS[i] = [];
  }
  for (var i = 0; i <= n; i++) {
    for (var w = 0; w <= capacity; w++) {
      if (i === 0 || w === 0) {
      //让第一行和第一列为0，因为第一行和第一列表示容量为0或没有物品可装
        KS[i][w] = 0; 
      } else if (weights[i - 1] > w) {
        KS[i][w] = KS[i - 1][w]; //当前物品重量大于当前容量
      } else {
       //当前物品重量小于当前容量，有两个选择，装或者不装，取价值最大的
        a = KS[i - 1][w - weights[i - 1]] + values[i - 1]; //装入这个物品后的总价值
        b = KS[i - 1][w]; //不装
  
        KS[i][w] = a > b ? a : b;
      }
    }
     
  }
  return KS[n][capacity];
}

测试

var values = [3,4,5,8,10];
var weights = [2,3,4,5,9];
var capacity = 20;
var n = values.length;
console.log(kanpSack(capacity, weights, values, n)); //26

这个算法构造了一个二维表格KS，存储了递归过程的中的值，即用for循环代替了递归，表格右下角的最后一个格子就是问题的解。