彻底搞懂动态规划解01背包问题

##引子 在大学的时候，有数据结构与算法的课程，课程中也会讲到01背包问题，那时只是一知半解，想当然认为是这样，但是要真正理一下里的流程，又无从下手 ，于是痛定思痛，重新去google了一番，终于有所领悟。

##问题还原 一个背包，承重为W。现在有一堆不同的石头，每块石头的重量和价值都不一定相同，也就是说不是确定的，问题是如何装，才能确保包里面的石头最有价值。

问题的描述可能还有其它版本，有些版本是用体积的。比如背包的体积是V，每块石头的体积和价值都不一定相同。我这里暂用重量吧，都是一个意思。

##思考 如果这是一个无界背包问题，就是指，石头是可以切割的，那我们可以用贪心算法来做，算出每块石头的单位重量价值，优先把价值高的石头放进去，如果超重的话， 就把这个超重的石头给切了刚好放满就能解决问题了。

01背包问题和无界背包有点不同，不同点在于，石头不能切割，对于一块石头而言，只能有2种选择，放进去与不放进去，莎士比亚说过：“be or not to be that is a question”，用来形容这个问题很形象。

我们先抽象一下问题的解，设f(n,w)为01背包问题的解，n为前n个石头，w为背包最大承重，这里并不是说就肯定把n个石头都放进去，显然和问题相悖,n指的是有n 个石头可选择。f(n,w)也就是在有n个石头可选择的情况下，放入承重为w的背包中，背包内有最大价值的最优解。

###分析 我们来分解下面几种情况

1. 当w为0时，即不管有几个石头，这个包什么都不能装，显然f(n,0)=0;
2. 当n为0时，即不管这个包能承重多少，没什么物品可选，显然f(0,w)=0;
3. 当w,n都不为0时，我们可以看看n-1的情况;
   • 当我们不把第n个物品放入背包时，背包的价值为f(n-1,w)
   • 当我们把第n个物品放入背包时，因为这个石头占了背包的承重，所以我们要解决的问题就是之前n-1个石头放入承重为w-wn的包的解,即此时背包的价值为vn+f(n-1,w-wn);
   • 我们分析了放与不放的情况，接下来我们就取两者的最大值做为解吧即f(n,w)=Max(f(n-1,w),vn+f(n-1,w-wn));

当然，不要忘记一个约束条件，就是任何时候都不要过载哦。