一、经典问题：背包问题

小偷去某商店盗窃，背有一个背包，容量是50kg，现在有以下物品（物品不能切分,且只有一个），请问小偷应该怎么拿才能得到最大的价值？
重量 价值
物品1 10kg 60元 60 / 10 = 6
物品2 20kg 100元 100/20 = 5
物品3 40kg 120元 120/40 = 3
性价比最高：贪心的策略，按性价比排序,得到的最大价值是 60+100=160，背包装了30kg
很显然：40+10（kg）=120+60=180
如果用贪心可以解决问题吗？
不能,如果从解决现实种问题的来说，你就按你自己的的想法拿。

通过分析，上面的背包问题通过贪心是解决不了的，很显然如果我们每次拿性价比最大的那么就只有160，而最大应该是220，这就是贪心算法的局限性，那么这个问题该如

1.穷举解决：

价值：60 100 120
重量：10 20 30
背包是50kg：
遍历它：每个物品只有2个选择就是拿与不拿吧，我们就用枚举，排列组合；
3：000 111 011 010 001 100 101 110 ，有没有道理. 10个物品 有多少排列组合？10! 20!,10一下是完美的，32！

上面通过循环得出各种情况的最大值，我们只要对最后的结果进行选取就可以了，但这样当物品多的时候，效率就很低了。

2.动态规划解决

核心是把大的问题分成小问题去处理，确保每个小问题都找到最优解，然后用状态转移方程实现大问题的最优解。
5kg的袋子
物品：
钱：6 10 12
Kg：1 2 4
我们把5kg的袋子，拆分成1kg，1kg这样子计算，里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品

加入物品2时，袋子当前为1kg 的容量时，我们发现物品2装不进去。那我们应该取多少呢？是不是只要取物品进来时1kg最大钱？，当袋子为2kg时，我们发现物品2可以装下去，此时可以得到10块钱，之前物品1进来时2kg最大是6吧，那我们肯定要选择大的这个10，而不是6.此时袋子还剩0kg可以装。
袋子为3kg时，我们还是可以装下这个物品2,得到10块，袋子还剩下1kg。
10+1kg能装的东西。
物品3来了，袋子为4kg时，物品3可以转进来，得到12块钱，袋子还剩0kg。
我发现我不装物品3 还能得到16呢
物品3来了，袋子为5kg时，物品3可以转进来，得到12块钱，袋子还剩1kg。那么装了物品3就能得到12+6=18块钱
我发现我不装物品3 能得到16，比18小，所以决定装。
上面这一个递推过程总结起来就是一个东西———状态转移方程：
能装的时候每次和上面的比较，大我就装，否则就不装。
Max(money[i]+res[i-1][w-weight[i]],res[i-1][w]);
money[i]+res[i-1][w-weight[i]]:装这个物品
w-weight[i] :表示装完还剩下的空间
res[i-1][w-weight[i]]:表示装完后剩下的空间还能装的最大值，取上一次的结果。
Res[i-1][w]表示不装这个物品的值
和遍历的比较及优化：
遍历每次在物品加进来的时候都会保存选择与不选择两种状态那么这样下去越到后面状态保存的就越多其实就是2^n次，因为每个物品都有选与不选两种情况。而动态规划是每次都会把当前情况下的最优解计算出来，层层递推，下一层的最优解都是基于它上一次结果存下来的，所以最后一个结果就一定是最优解。
其实也是把问题都分解成了一个子问题，然后通过子问题去求解全局最优解。

最后

（1）贪心解决不了就用动态规划，一般贪心算法的时间复杂度为O(nlgn)，动态规划为O(n^2)，能用贪心解决就不用动态规划。
（2）贪心得到的结果不一定是最优解。
（3）动态规划在分析子问题的时候，会使用前面子问题的最优结果，并且前面子问题的最后结果不受后面的影响，最后一个子问题即最优解。