JavaScript 01背包问题动态规划

问题描述

有n个物品，每个物品的价值为value[n]，每个物品的重量为weight[n]，有一个背包最大可以放w重量的物品。
问：把哪几个物品放入背包可以使得背包的价值最大。
其中，物品只有一个，可以放入背包，也可以不放入；不能把物品拆分开；物品的状态只有01两种，所以叫01背包问题。

具体示例

有一个背包，重量为10；有5个物品，重量数组为weight=[2，2，6，5，4]，价值为value=[6，3，5，4，6]，请问背包最大价值是多少？

示例解析

建立矩阵来存放分析结果（n:物品序号；w:背包重量）

weight	value	n/w	0	1	2	3	4	5	6	7	8	9	10
2	6	0
2	3	1
6	5	2
5	4	3
6	6	4

分析第一行：
看第一行，表示只有物品0时，背包重量分别为0~10的时候，价值是多少，这一行是边界条件
当背包重量为[0,1]时，放不进东西去，所以价值是0
当背包重量是2~10时，能把物品0放进去，所以价值都是6

weight	value	n/w	0	1	2	3	4	5	6	7	8	9	10
2	6	0	0	0	6	6	6	6	6	6	6	6	6
2	3	1
6	5	2
5	4	3
6	6	4

由此，我们可以得出这一步的方程式：

以下所有方程都规定：

• T[x][y]：背包的最大价值
• c：背包的重量
• w[I]：第i个物品的重量
• v[i]：第i个物品的价值

分析第二行

• 当背包重量为[0,1]时，放不进东西去，所以价值是0
• 当背包重量是2~10时，能把物品0放进去，进一步分析：
  • 当背包重量是2时，可以放进去物品0或者物品1，比较放入物品1和不放入物品1哪个价值大，发现放入物品1价值小于不放入，所以将物品0放进去。这时候，T[1][2] = T[0][2]。背包重量为3~10时，依次查看放入物品1价值是否更大。

由此得出以下表格

weight	value	n/w	0	1	2	3	4	5	6	7	8	9	10
2	6	0	0	0	6	6	6	6	6	6	6	6	6
2	3	1	0	0	6	6	9	9	9	9	9	9	9
6	5	2
5	4	3
6	6	4

由此进一步得到递归方程：

分析第三行到第五行，依次填入表格
分析过程是：

• 分析新的物品放入背包（能放得下的情况下），背包的价值是否大于不将最新物品放入的价值，如果大，就放入，如果小，就舍弃

最终表格如下

weight	value	n/w	0	1	2	3	4	5	6	7	8	9	10
2	6	0	0	0	6	6	6	6	6	6	6	6	6
2	3	1	0	0	6	6	9	9	9	9	9	9	9
6	5	2	0	0	6	6	9	9	9	9	11	11	14
5	4	3	0	0	6	6	9	9	9	10	11	13	14
6	6	4	0	0	6	6	9	9	12	12	15	15	15

由此：最终的方程式应该是：

代码

第一版代码（参考司徒正美大佬的代码）

/**
 * @desc 01背包问题 原始代码
 * @param {Number} w 背包的重量
 * @param {Array} weightArr 每个物品的重量
 * @param {Array} valArr 每个物品的价值
 * 参考：https://segmentfault.com/a/1190000012829866
 */
var backpack = function (w, weightArr, valArr) {
  // 物品数量，从0开始
  let n = weightArr.length-1
  // 保存结果的二维数组
  let tmpArr = [[]]
  // 只有一个物品的情况
  for (let a = 0; a <= w; a++) {
    // 这个物品装不进去（边界情况）
    if (a < weightArr[0]) {
      tmpArr[0][a] = 0
    } else {  // 这个物品可以装进去（边界情况）
      tmpArr[0][a] = valArr[0]
    }
  }

  // 有好几个物品的情况
  // 循环背包容量
  for (let j = 0; j <= w; j++) {
    // 循环物品个数
    for (let i = 1; i <= n; i++) {
      // 创建新行
      if (!tmpArr[i]) tmpArr[i] = []
      // 最后一个装不进去，所以最大值为前i-1个的最大值
      if (j < weightArr[i]) {
        tmpArr[i][j] = tmpArr[i - 1][j]
      }else{ // 最后一个能装进去，找装与不装的最大值
        tmpArr[i][j] = Math.max(tmpArr[i-1][j], tmpArr[i-1][j-weightArr[i]]+valArr[i])
      }
    }
  }
  console.log(tmpArr[n][w]) 
}

优化一：合并循环（参考司徒正美大佬）
上述代码中，有两个循环，可以件他们合成一个，也就是将边界情况合并到循环里边

var backpack = function (w, weightArr, valArr) {
  // 一共有几个商品
  let n = weightArr.length
  // 创建一共有n个元素的空数组，保存结果
  let tmpArr = new Array(n);
  // 创建二位数组
  for(let a=0; a<n; a++) tmpArr[a] = []
  // 循环物品
  for(let i=0; i<n; i++){
    // 循环背包容量（从0~w）
    for(let j=0; j<=w; j++){
      if(i===0){  // 只有一个物品时
        tmpArr[i][j] = j<weightArr[i] ? 0 : weightArr[i]
      }else{ // 有多个物品时，要根据以前最好的情况继续算
        tmpArr[i][j] = Math.max(tmpArr[i-1][j], tmpArr[i-1][j-weightArr[i]]+valArr[i])
      }
    }
  }
  return tmpArr[n-1][w]
}

• 因为第一行（边界条件那里）f[i][j] = j < weights[i] ? 0 : values[i]也能适用于下面这一行f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])，所以方程式也可以简化为：

此时，增加一个-1行来进一步优化代码：

// 这个技巧可以仔细研究一下
var backpack = function(w, weightArr, valArr){
  let n = weightArr.length
  let tmpArr = new Array(n)
  tmpArr[-1] = new Array(w+1).fill(0)  // 增加一个-1行，全部填充成0，这时候就符合最终的方程式了。这里是重点！
  for(let i=0; i<n; i++){
    tmpArr[i] = new Array(w).fill(0)
    for(let j=0; j<=w; j++){
      if(j<weightArr[i]){
        tmpArr[i][j] = tmpArr[i-1][j]
      }else{
        tmpArr[i][j] = Math.max(tmpArr[i-1][j], tmpArr[i-1][j-weightArr[i]]+valArr[i])
      }
    }
  }
  console.log(tmpArr[n-1][w])
}

backpack(10, [4, 3, 5, 2, 5], [9, 6, 1, 4, 1])
backpack(10, [2, 2, 6, 5, 4], [6, 3, 5, 4, 6])
backpack(5, [2, 3, 4], [3, 4, 5])
backpack(10, [5, 3, 4, 3, 5], [500, 200, 300, 350, 400])

进一步优化还没研究明白，以后更新

参考：
https://segmentfault.com/a/1190000012829866