前言

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

正文

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

话说地主金馆长家有个专门藏金银财宝的房间,潜入后发现可偷之物太多,奈何自身负重能力有限,你的包只能承重 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 件物品呢?那么拿不拿的前提是啥?当然是这个物品重不重,能不能塞到包里。所以第一种情况就出现了:

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

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

  1. 不拿 k 号物品,那么此时包中物品的总价值b(k,c)=b(k-1,c),和第一种拿不动 k 号物品的一样。
  2. 拿走 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背包问题的图解 但是我当时看的时候真的是一脸懵逼,然后再带着图去看长篇的解析就更混乱了。希望你能在理解了上述流程之后,再回过头去看公众号之前的文章,对那个图的理解应该就会更加深刻了,二者一起看,辅助理解。

推荐

  1. 推荐一个良心视频,讲解的也很详细——01 背包问题
  2. 推荐一个在线查看解决“01 背包问题”的网站,详细的描述了变化过程Online 0/1 Knapsack problem solver

如果你觉得本文还不错,麻烦随手点赞与转发吧。😋(扑通

点赞与转发是最好的支持