前端学习算法2: 背包问题 ，一步一步思考（动态规划入门）

1 背包问题

先举一个很通俗易懂的例子，也是图解算法中的例子，有一个只能装4kg的包，物品有音响3000元-重4kg，吉他1500元-重1kg，电脑2000元-重3kg。问，要想包里的价值最高，应该怎么装？（注意：不考虑 物品的体积，不要想吉他很大放不下。）

1.1 解答

相信这个例子，随便看一下就可以知道要装什么，肯定是装电脑加吉他。总价值3500块，又刚好4kg。

1.2 为什么？

拜托，这么简单的题目，看一眼就知道为什么了。因为其余的组合情况，不可能比这个价值高的，即使比这个价值高，那也放不下了。很好，这就是最简单的暴利穷举算法了。红色的情况是超重了，放不下。

也就是说，物品数目是3的时候，有2^3种情况，然后找到符合条件的，也就是背包放的下的情况，取出价值最大的组合即可。 那么假如是4种商品呢，或者5种呢？这种组合情况是不是分别为2^4 2^5种，就很难一眼看出结果了吧，虽然上述逻辑对，但是这种 2^n 指数的量级 ，也未免也太复杂了。

2 动态规划登场

上一篇动态规划入门的文章里有写过，动态规划，就是大事化小，小事化了。那么对于这种类型的题目，要怎么化繁为简呢？要怎么找出有代表性的模型呢？

2.1 我们来思考一下

现有背包载重量为4kg，这个背包已经装了现有情况下价值最高的物品，价值为v1。那么，在这个情况下，有一个 新的物品 ，这个物品的重量是x kg，价值是v，那么此时对于这个4kg的包，装物品的最大值，分几种情况呢？

1. 先来看看由于新物品的出现，这个4kg的包要怎么装？ 太多种情况了，但是要想装的物品价值总和最大，那么一定是符合接下来说的这种情况的。这里我们不用考虑x>4的情况。
2. 假如要装这个新物品，那么装了后剩余的载重量为(4-x)kg，假设这个载重量，能装的物品最大值是v2 ，此时这个4kg的包，所能装载的物品最大价值就是v+v2
3. 假如不装这个新物品，那4kg的包所能装载物品的最大值还是v1。
4. 所以此时的4kg包装物品最大值是v1或者v+v2

2.2 继续思考

1. 那4-x有多少种可能呢，1kg 2kg 3kg ，由上述前提，我们已经知道了载重4kg的包能放物品最高价值是v1。而对于1kg 2kg 3kg这种简单情况所能承载的物品最高价值，也是可以通过上述的方式去推导得出的。

3 复杂一下题目

有一个载重量是10kg 的背包，有五个物品，a 2kg 6元，b 2kg 3元，c 6kg 5元，d 5kg 4元，e 4kg 6元。问怎么放物品，价值最高？

根据上面的推导，我来画一些表格

1. 首先我们 只有a物品 ，然后1-10kg的包，对于只有a物品的情况，如下：解释一下表格组成，尤其是最左边一列，代表着依次 新有的物品 ，上面一行是承载量不同的背包值，剩余的是当前承载量下，对应拥有的物品的最高价值。

   

2. 那么此时有了 b物品（此时共有a b两个物品可以选择） ，想一下上面的推导的结论，填完表格，如下

结合之前推导的结论，来以2kg那一列说明一下，第一个6元，是只有a物品时候，那么此时能放进背包的最高价值就是6元。当有了b物品可以选择时，有两种情况，（1）放进b物品，包的载重量-b物品重量后为0，然后加上b物品价值是3元（2）不放b物品原来价值是6元，取最大，即6元。

3. 那么此时有了 c物品（此时共有a b c三个物品可以选择） ，这里不做解释，直接上图

随便抽出1个节点的值来验证一下吧:

7kg时候，已经从abcd挑选结束，现在要考虑新增e的情况。 那个一直7kg时候，最高价值10元，新增的物品e是4kg，假如放了e，那么剩余空间是3kg，由图可知，在没有e之前，3kg的包最大能放6元物品。e的价值是6元，所以加起来12元，大于之前的最高值10元，所以对应的左标填值12元

4 代码实现

//by 司徒正美
function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        if(j < weights[0]){ //如果容量不能放下物品0的重量，那么价值为0
            f[0][j] = 0
        }else{ //否则等于物体0的价值
            f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    console.log(f)
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)
复制代码

最终打印的结果如下

(希望自己能一直坚持下去吧~~)

参考：

1. 司徒正美文章 segmentfault.com/a/119000001…
2. 算法图解 动态规划一章