做小偷也要会动态规划——轻松解决"01背包问题"

前言

小偷不可怕，就怕小偷有文化，更怕小偷学过动态规划。

正文

白玉汤曾是江湖上赫赫有名的盗圣，奈何岁月不饶人，上了年纪后腿脚便不利索了，无奈一身的本领却没有个传承之人。这天，一位少年前来拜师学艺，希望白玉汤能在偷盗一事上指点一二。白玉汤见这少年骨骼清奇，内心有收其为徒的想法，便出了下面这道题考考少年：

话说地主金馆长家有个专门藏金银财宝的房间，潜入后发现可偷之物太多，奈何自身负重能力有限，你的包只能承重20kg的物品，而且每个物品的价值又都不一样，那么问题来了，将哪些物品装入背包才能不虚此行，使价值总和最大呢？物品重量和其价值的关系如下：

编号	重量（w）	价值（v）
1	2	3
2	3	4
3	4	5
4	5	8
5	9	10

少年一看，这不就是一道“01背包问题吗”，说完便在地上做出了如下分析：

设我们的背包里面的物品价值为b，给背包添加两个参数：k和c，即b(k,c),那么b(k,c)又表示什么什么意思呢？

k表示你面对的物品编号，即1~5,
c表示你面对k号物品时，背包的剩余容量
b(k,c)表示面对k号物品，并作出拿或不拿的选择之后，背包里面的物品总价值

举个例子，b(2,20)表示的是，在你的背包容量为20的情况下，当你面对2号物品时并作出拿或者不拿的选择后，背包中物品的总价值。

了解了这个概念后我们继续：
假设你现在遇见了第k号物品，此时你的背包容量为c，你得做出一个决策，到底要不要拿走第k件物品呢？那么拿不拿的前提是啥？当然是这个物品重不重，能不能塞到包里。所以第一种情况就出现了：

如果第k件物品的重量w[k]比此时的背包的剩余重量c大了，那我肯定是拿不动了，即w[k]>c。所以此时包中物品的价值就是我拿的前一个物品之后包中的价值，即 b(k,c)=b(k-1,c).包中剩余空间不变，还是c。

那么第二种情况，如果我拿得动第k件物品，即第k件物品的重量w[k]<c，面对k号物品，无外乎两种选择，拿或者不拿，这时我就要根据拿走之后产生的效益进行决策了：

不拿k号物品，那么此时包中物品的总价值b(k,c)=b(k-1,c)，和第一种拿不动k号物品的一样。
拿走k号物品，那么此时包中物品的总价值b(k,c)=b(k-1,c-w[k])+v[k]拿了第k件物品后，那我的包中的价值肯定就是原先的价值再加上第k件物品的价值，而且拿了之后包中的剩余容量就为c-w[k]了。总结一下，就是如下的公式了：b(k,c)=max{b(k-1,c),b(k-1,c-w[k])+v[k]}

剩下的只需要比较小这两种方式谁的效益大即可。思维导图如下：

01背包问题的递推公式

看懂以上描述后，编码就很简单了，这里我用Java写出来

class Main {
    public static void main(String[] args) {
        int[] w = { 0, 2, 3, 4, 5, 9 };
        int[] v = { 0, 3, 4, 5, 8, 10 };
        int N = 6, W = 21;
        int[][] b = new int[N][W];
        for (int k = 1; k < N; k++) {
            for (int c = 1; c < W; c++) {
                if (w[k] > c) {
                    b[k][c] = b[k - 1][c];
                } else {
                    int value1 = b[k - 1][c - w[k]] + v[k]; // 拿第k件物品
                    int value2 = b[k - 1][c]; // 不拿第k件物品
                    b[k][c] = Math.max(value1, value2);
                }
            }
        }
        System.out.println(b[5][20]);
    }
}

结果为26

最后

其实公众号之前有发过一篇类似的“01背包问题”的解析——《使用动态规划解决童年难题》，网上大多数的博客在解析“01背包问题”时也都是采用画图的形式，类似于这样的：

01背包问题的图解

但是我当时看的时候真的是一脸懵逼，然后再带着图去看长篇的解析就更混乱了。希望你能在理解了上述流程之后，再回过头去看公众号之前的文章，对那个图的理解应该就会更加深刻了，二者一起看，辅助理解。

做小偷也要会动态规划——轻松解决"01背包问题"

前言

正文

最后

推荐