连续背包问题：
还是先讲一段故事吧。假如你是一个贼，有一天你去地主家偷东西。有4斤金沙，2斤银沙，10斤铜沙。
但是运气不好的是，你的包只能装8斤东西。那么你该偷什么走呢？
我们这边把这个问题分解成 方程式和约束条件
方程式：gx + sy + cz --->max #gsc分布代表金银铜
约束条件：x+y+z = 8
g>s>z
max(g)=4 max(s)=4 max(c)=4
这里这个问题，是贪心算法的主场，当然有很多解决问题的方法，我们的目的就是找到最优秀的解，我们先保证装足够多的金子，然后如果金子装完了，
而且还有剩余空间的话，就装足够多的银子。。。。在连续问题里，贪心算法的确可以得到最优解，贪心算法的核心就是就是保证局部的优越性，、
但是保证局部的优越性，并不能保证整体的优越性。我们这边先不深入说贪心算法。我们接着说背包问题。
0/1背包问题：
有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]
这里我们当然可以用贪心算法，和穷举算法，
但是它们都有一个致命的缺点 贪心算法：往往得不到最优解 穷举花费的时间又太多了{指数级别}
这里就需要一个新的算法了---》动态规划(dynamic programming)--->本质上它是对穷举算法的优化
动态规则：首先不要通过他的名字去理解它，它只是一个名字而已，呵呵
好累呀、、、、要不要先休息一会。
我们先谈论子结构的问题吧
def fib(n):
global numCails
numCails +=1
print "numCails-->",numCails
print "n---->",n
if n <=1:
return n
else:
return fib(n-1) + fib(n-2)
我们先看这段代码，如果我传了fib(5). 他会递归 n-1 n-2 然后接着。
这段代码的问题就是，他有很多重复的子结构
这个是fib(5)的输出，你可以看到他有很多相同的子结构
numCails--> 1 n----> 5 numCails--> 2 n----> 4 numCails--> 3 n----> 3 numCails--> 4 n----> 2 numCails--> 5 n----> 1 numCails--> 6 n----> 0 numCails--> 7 n----> 1 numCails--> 8 n----> 2 numCails--> 9 n----> 1 numCails--> 10 n----> 0 numCails--> 11 n----> 3 numCails--> 12 n----> 2 numCails--> 13 n----> 1 numCails--> 14 n----> 0 numCails--> 15 n----> 1
那么dp是如何解决的呢？
我们先看下图 我们要从A-F
一共有多少中方案呢？
这个是一个很简单的问题 但是不知道你有没有关注到D 这个重合节点的。
而dp的核心就是寻找最优子结构，说白了就是没有重合的子结构。
http://www.cnblogs.com/nerdlerss/p/5645552.html
{未完待续}