0/1 背包问题
问题描述：给定一个容量为 C 的背包及 n 个重量为 wi，价值为 p1 的物品，要求
把物品装入背包，是背包的价值最大，此类问题为背包问题。物品或者装入背
包，或者不装入背包，称之为 0/1 被包问题
假设 xi 表示物品 i 被装入背包的情况，xi = 1 表示物品装入背包，xi = 0 表示物
品没装入背包，根据题目要求，有下列约束函数
SUM(wi*xi) <= C,bestp = MAX(pi*xi) where 0 <= i < n
解决方法：0/1 背包问题有多种解决方法，本实验用动态规划，回溯，分支界限
三种方法进行解题
动态规划：令 M(i,j)表示将前 i 个物品装入容量为 j 的背包中可获得最大价值，
显然在前 i 个物品中有的装入，有的未被装入。则得动态转移方程
M(0,j)=M(i,0)=0 (1)
M(i,j) = M( i – 1, j ) j < wi (2)
Max(M(i–1,j),M(i–1,j–wi)+pi) j >=wi (3)
式(1)表示将 0 个物品装如容量为 j 的背包或者将 i 个物品装入容量为 0 的背包所
得的价值均为 0
式(2)表示第 i 个物品的重量大于背包的容量，则装入前 i 个物品的最大价值与装
入前 i – 1 个物品的最大价值一样（即第 i 物品没有装入）
式(3)表示第 i 个物品重量小于背包的容量，则装入前 i 个物品的最大价值等于将
第 i - 1 个物品装入容量为 j - wi 的背包所得的价值加上第 i 个物品的价值与
将前 i – 1 个物品装入容量为 j 的背包中所得的价值的最大值
回溯+减枝：令问题的解向量为 X = (x0,x1,….,xn-1),使用回溯法求这个解向量，
状态空间树是一棵完全二叉树节点总数为 2^n + 1 – 1,从根节点到叶
子节点构成问题的所有可能状态，假定第 i 层的左儿子子树描述物
品 i 被装入背包的情况，右子树描述物品 i 没被装入背包中，0/1 背
包问题求的是一个最优解，在构造解的时候加上约束条件可减少搜
索空间。在搜索的时候尽量沿着左子树进行，当不能沿着左子树搜
索的时候得到一个解，此时移到右子树搜索，如果理想价值大于当
前最优解，则进入右子树搜索
直到找到一个可行解。刷新最优解，并向上回溯。如果理想价值小于当
前最优解，则抛弃右子树
约束条件：从当前物品 i 可得到理想价值。假定已取得的解向量为 X = (x0,x1,…
xk)，当前价值 cp,背包剩余容量 cleft,期望值 Expect = cp + SUM(pi)
where k =<i < n 且 wi <= cleft - SUM(wi) >= 0 + (pi/wi)*cleft
例：用容量 C = 50 的背包，物品重量分别为 5,15,25,27,30,物品价值分别为
12,30,44,46,50,求最有装入背包的物品及价值
其状态搜索空间如下：
