自认为背包dp理解的还不错，至少这是我去年第一次在社团讲的内容，所以感觉自己还是有一些不错的理解的，所以决定和大家分（骗）享（骗）分（访）享（客）。

问题描述：

现在，有n件物品，已知这n件物品的体积分别为： v 1 、v 2 ...v n−1 、v n   然后，这些物品对应的价值为： w 1 、w 2 ...w n−1 、w n   。你可以从中任意选取若干个，放到一个容积为 V  的背包中，然后带回家。现在就问你，最多可以带价值为多少的物品回家。（可以装不满背包）

分析：

首先就是，最简单的办法就是，我可以暴力的枚举每一种可能的选择方法：每一个物品我都有选和不选两种选择，那么我一共就有 2 n   种不同的选择方式。

但是当n比较大的时候，相信大家已经可以看出时间复杂度呈指数增长，1s的时间内，我们大概只能解决 n≤30  的情况，但是我们总是希望可以尽量解决规模更大的问题。那么，我们就考虑一下 n=1000  的时候：

此时如果我暴力枚举，那么就有 2 1000   种选择方式，那么现在，我们就想一想枚举所有的这些选择方式我进行了哪些重复的计算或者不必要的计算呢？
1.首先我们可以想到一个问题，就是我枚举了好多超出背包容积的情况，比如一共有50个物品，假设在前20个都装进去了的前提下，就已经满了（或者接近装满），但是，我还是枚举了后面30个物品的每一种组合情况（ 2 30   种）。这些工作都是不必要的。那么我们是不是可以想办法舍去这些枚举呢。这将是一个很不错的优化。
2.其次，你会发现一个事情，就是这1000个物品，装到容积为10000的背包里，枚举每一种组合的话，一共 2 1000   种情况，组合爆炸，除去超出最大容积的情况之外，剩下的情况有可能还是很多很多。但是这些情况组合出来的所需的体积都一定是1-10000之间的一个数。也就是说，因为我最后只关心的是总价值，所以我可以把 2 1000   种选择方式对应到这10000种总体积上面，那么平均每种体积，应该是要对应 2 985   种组合方式左右。那么如果我可以把这 2 985   种组合方式合并成一种，那么这一定是一个极大的优化！
综合上面两个原因，我就可以考虑从体积来入手，把多种总价值相同的选择方式合并成一种，这样我就减少了很多重复性的枚举操作。

那么，我现在就并不关心组合方式的问题了，因为我只需要知道可能得到的最大价值。
现在我知道，肯定有一种选取方式，可以得到从前 n  个物品中选取若干个装到容积为 V  的背包中获得的最大价值。那么，这种最佳的选取方式有没有选最后一个物品 （v n ，w n ）  呢？
我把情况分成两种：
（1）得到最大价值的选取方式中选取了最后一个，那么这个问题就相当于如何选取可以于从前 n−1  个物品中选取若干个装到容积为 V−v n   的背包获得的最大价值;
（2）得到最大价值的选取方式中没有选取最后一个，那么这个问题就相当于如何选取可以从前 n−1  个物品中选取若干个装到容积为 V  的背包获得的最大价值;

那么我们就得到了一个状态转移方程：

电脑快没电了，我明天再继续写。