北京市治疗白癜风 http://m.39.net/pf/a_4491886.html0-1背包问题背景
我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
背包问题
递归算法
假如背包的容量是C=6，物品的体积为w，对应的物品的价值为v。我们从最后一个物品开始，如果它的体积比背包剩余容量小，它面临着两种选择：1，放进背包；2，不放进背包。
如果它的体积比背包剩余容量大，那么就不能放进背包，n往前走。如上图所示，每个物品都面临着这种选择，直到n0,即没物品可放。
下面为背包问题的递归算法。
递归算法的问题是，有好多的重复计算，时间复杂度为2的n次方，n为物品数量。
动态规划算法
动态规划跟递归非常相似，不同的地方在于使用一个数组来记录已经计算过的，避免重复计算。
在上面代码中假如4行后就变为动态规划了，时间复杂度也变为O(n*c)
