前言

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

正文

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

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

少年一看，这不就是一道“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]}

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

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

最后结果是26.

题外话

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

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

最后

点赞与转发是最好的支持，如果你觉得本文还不错，麻烦随手点赞与转发吧。