题目：
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
实例1：
假设有一个32m³的包，然后有3个物品 A(2, 8m³),B(2.4, 27m³), C(4,27m³)
分析：
- 最容易想到的应该暴力破解了：这里的可行组成
A（2），B（2.4），AB（4.4），C（4）；一下就出来了肯定就是AB了；
但是这个随着数据量的变大就会非常慢，他的时间复杂度是O(2^N) - 如果按照贪心算法的思路，将价值比最大的物品先放入是不是就可以了，每个物品的价值比就是 A:0.25r/m³, B: 0.088r/m³,C: 0.14r/m³ 每次选取最优那就是C了，连结果都是错误的；
在讲解正解时，先思考一个问题，如果让你在现实生活中操作，你会怎么搞；先拿第一个放进包了，然后在那第二个这时首先是考虑一个问题这个包还能不能放进这个物品，要是不能，那能不能将之前放入的拿一些出来再将他放回去，还有这样做是不是最优。。。好复杂，有这样那样的问题；
换个思路来思考；假设一个物品必须要放进包了，怎么才能使它价值最大，就是剩下的空间里装的物品组合起来价值要最大；那剩下空间里装什么物品组合在一起价值才会最大呢；问题好像又回来了，但是出现了变化，那就是空间变小了；组合也就少了，诶，事情出现了眉目，如果包只有8m³ ，那就只有一种选择就是A了；这样最初的蛋不是找到了吗？那为了方便记录不同空间的最优组合，画张表，方便查找
注：为了跟方便的体现这个思路换一个示例
有4m³大小的包，A（30,4m³），B（20,3m³），C(15， 1m³)
| 1m³ | 3m³ | 4m³ | |
|---|---|---|---|
| C | 15 | 15 | 15 |
| B | 15 | 20 | 35 |
| A | 15 | 20 | 35 |
解释一下这个表格：行代表不同容积的包，列代表在这个容积下的具备不同物品时的能装下最大的价值(第一行代表只有物品C，第二行代表具备C物品时增加了B物品，第三行代表具备BC物品时增加了A物品)；
这里讲解一下最后一个单元格（其它的应该都不难理解）；最后一个单元格；物品A有两种状态：放入与不放入；要放入就是30，因为它刚刚装满背包；不放入就是上面的单元格35，一比较还是不放入吧！
相信看到这里有些人还会有点疑惑！再加入一个物品D（20,1m³）
那它的表格就是
| 1m³ | 3m³ | 4m³ | |
|---|---|---|---|
| C | 15 | 15 | 15 |
| B | 15 | 20 | 35 |
| A | 15 | 20 | 35 |
| D | 15 | 35 | 40 |
还是来讲解最后一个单元格；这里物品D有两种可能：放入或不放入
不放入那就是上一个单元格 35；
那放入能就是 20 + （4-1m³ 下能装的最大价值 = 20）这里有人可能会问为什么不是加35因为这里的物品都只有一件；如果是不限个数就是加35（完全背包问题）
然后取两种可能的最优就是 40了
dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])
具体详细的还请看这里；极度推荐
解法就不提了
这里的分治思想很是巧妙，将空间和物品从小到大，将问题限制在 这个物体的价值+这个物体放置后剩余空间剩余物体的最优组合解上；而剩余空间剩余物体的最优组合解 是一个极小有穷解