做小偷也要会动态规划——轻松解决"01背包问题&quo
前言
小偷不可怕，就怕小偷有文化，更怕小偷学过动态规划。
正文
白玉汤曾是江湖上赫赫有名的盗圣，奈何岁月不饶人，上了年纪后腿脚便不利索了，无奈一身的本领却没有个传承之人。这天，一位少年前来拜师学艺，希望白玉汤能在偷盗一事上指点一二。白玉汤见这少年骨骼清奇，内心有收其为徒的想法，便出了下面这道题考考少年：
话说地主金馆长家有个专门藏金银财宝的房间，潜入后发现可偷之物太多，奈何自身负重能力有限，你的包只能承重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背包问题
- 推荐一个在线查看解决“01背包问题”的网站，详细的描述了变化过程Online 0/1 Knapsack problem solver
如果你觉得本文还不错，麻烦随手点赞与转发吧。😋（扑通
image
点赞与转发是最好的支持
