问题描述0/1 背包问题 :现有 n 种物品，对 1<=i<=n ，已知第 i 种物品的重量为正整数 W i ，价值为正整数 V i ， 背包能承受的最大载重量为正整数 W ，现要求找出这 n 种物品的一个子集，使得子集中物 品的总重量不超过 W 且总价值尽量大。

(注意：这里对每种物品或者全取或者一点都不取， 不允许只取一部分)算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：nw i x i W i 1 i i(1)x i { 0,1}( 1 i n)nmax v i x i (2) i1于是，问题就归结为寻找一个满足约束条件( 1 )，并使目标函数式( 2 )达到最大的 解向量 X (x 1, x 2 ,x 3, ........... , x n ) 。

首先说明一下 0-1 背包问题拥有最优解。

假设 (x 1,x 2,x 3, ........ ,x n ) 是所给的问题的一个最优解， 则(x 2,x 3, ............... ,x n )是下面问题的n n n个问 题 的 一 个 最 优解 ， 则v i y iv i x i ， 且 w 1x 1w i y i W 。

因此 ，i 2 i 2 i 2一个最优解：w i x i Wi2w 1x 1nmax v i x i 。

如果不是的话，设(y 2,y 3, , y n ) 是这x i {0,1}( 2 i n)i2n n nv1x1 v i y i v1x1 v i x i v i x i ，这说明(x1,y2,y3, ............. ,y n) 是所给的0-1 背包问i 2 i 2 i 1题比( x1 , x 2 , x3 , ... , x n ) 更优的解，从而与假设矛盾。

穷举法：用穷举法解决0-1 背包问题，需要考虑给定n 个物品集合的所有子集，找出所有可能的子集(总重量不超过背包重量的子集) ，计算每个子集的总重量，然后在他们中找到价值最大的子集。

由于程序过于简单，在这里就不再给出，用实例说明求解过程。

下面给出了4个物品和一个容量为10 的背包，下图就是用穷举法求解0-1 背包问题的过程。

a) 四个物品和一个容量为10 的背包序号子集总重量总价值序号子集总重量总价值1空集009{2，3}7522{1}74210{2，4}837 3{2}31211{3，4}965 4{3}44012{1,2,3}14不可行5{4}52513{1,2,4}15不可行6{1，2}105414{1,3,4}16不可行7{1，3}11不可行15{2,3,4}12不可行物品1W2=3V2=12物品2W3=4V3=40物品3W4=5V4=25物品4背包W1=7 V1=12(b )用回溯法求解0-1 背包问题的过程递归法：在利用递归法解决0-1 背包问题时，我们可以先从第n 个物品看起。

每次的递归调用都会判断两种情况：(1 ) 背包可以放下第n 个物品，则x[n]=1 ，并继续递归调用物品重量为W-w[n], 物品数目为n-1 的递归函数，并返回此递归函数值与v[n] 的和作为背包问题的最优解；(2) 背包放不下第n 个物品，则x[n]=0 ，并继续递归调用背包容量为W ，物品数目为n-1 的递归函数，并返回此递归函数值最为背包问题的最优解。

递归调用的终结条件是背包的容量为0 或物品的数量为0. 此时就得到了0-1 背包问题的最优解。

用递归法解0-1 背包问题可以归结为下函数：KnapSack(n 1,m) 没有选择物品nKnapSack(n, m)KnapSack(n 1,m w[n]) v[n] 选择了物品n第一个式子表示选择物品n 后得到价值KnapSack (n 1,m w[n]) v[n] 比不选择物品n 情况下得到的价值KnapSack(n 1,m) 小，所以最终还是不选择物品n; 第二个式子刚好相反，选择物品n 后的价值KnapSack(n 1,m w[n]) v[n] 不小于不选择物品n 情况下得到了价值KnapSack ( n1,m) ，所以最终选择物品n。

在递归调用的过程中可以顺便求出所选择的物品。

下面是标记物品被选情况的数组x[n] 求解的具体函数表示：0 KnapSack (n, m) KnapSack ( n 1,m)x[n]1 KnapSack (n, m) KnapSack ( n 1,m w[n]) v[n]在函数中，递归调用的主体函数为KnapSack ，m 表示背包的容量，n 表示物品的数量，x[n]表示是否选择了第n 个物品( 1—选，0—不选)。

每个物品的重量和价值信息分别存放在数组w[n] 和v[n] 中。

具体的代码见《递归法》文件夹。

贪心法：0-1 背包问题与背包问题类似，所不同的是在选择物品i(1 i n) 装入背包时，可以选择一部分，而不一定要全部装入背包。

这两类问题都具有最优子结构性质，相当相似。

但是背包问题可以用贪心法求解，而0-1 背包问题却不能用贪心法求解。

贪心法之所以得不到最优解，是由于物品不允许分割，因此，无法保证最终能将背包装满，部分闲置的背包容量使背包单位重量的价值降低了。

事实上，在考虑0-1 背包问题时，应比较选择物品和不选择物品所导致的方案，然后做出最优解。

由此导出了许多相互重叠的子问题，所以，0-1背包问题可以用动态规划法得到最优解。

在这里就不再用贪心法解0-1 背包问题了。

动态规划法分析：0-1 背包问题可以看作是寻找一个序列( x1, x2, x3 , ............... , x n ) ，对任一个变量x i 的判断是决定x i=1 还是x i=0. 在判断完x i 1之后，已经确定了( x1, x2, x3 , ................. , x i 1) ，在判断x i时，会有两种情况：(1) 背包容量不足以装入物品i，则x i =0 ，背包的价值不增加；(2) 背包的容量可以装下物品i，则x i=1 ，背包的价值增加v i。

这两种情况下背包的总价值的最大者应该是对x i 判断后的价值。

令C(i, j) 表示在前i(1 i n) 个物品中能够装入容量为j (1 j W )的背包的物品的总价值，则可以得到如下的动态规划函数：C(i,0) C(0, j) 0(1)C(i 1, j) j w iC(i, j ) i(2)max{C(i 1, j),C(i 1, j w i) v i} j w i式(1)说明：把前面i个物品装入容量为0 的背包和把0个物品装入容量为j 的背包，得到的价值均为0.式(2)第一个式子说明：如果第i 个物品的重量大于背包的容量，则装入第i 个物品得到的最大价值和装入第i-1 个物品得到的最大价值是相同的，即物品i 不能装入背包中；第二个式子说明：如果第i 个物品的重量小于背包的容量，则会有两种情况： ( 1 )如果把第i 个物品装入背包，则背包中物品的价值就等于把前i-1 个物品装入容量为j w i的背包中的价值加上第i个物品的价值v i ；(2 )如果第i 个物品没有装入背包，则背包中物品的价值就是等于把前i-1 个物品装入容量为j 的背包中所取得的价值。

显然，取二者中价值较大者作为把前i 个物品装入容量为j的背包中的最优解。

我们可以一步一步的解出我们所需要的解。

第一步，只装入第一个物品，确定在各种情况下背包能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能够得到的最大价值；一次类推，到了第n 步就得到我们所需要的最优解了。

最后，C(n,W) 便是在容量为W 的背包中装入n 个物品时取得的最大价值。

为了确定装入背包的具体物品，从C(n,W)的值向前寻找，如果C(n,W)>C(n 1,W ) ,说明第n 个物品被装入了背包中，前n-1 个物品被装入容量为W w n的背包中；否则，第n 个物品没有装入背包中，前n-1 个物品被装入容量为W 的背包中。

依此类推，直到确定第一个物品是否被装入背0C(i, j) C(i 1, j)包为止。

由此，我们可以得到如下的函数：1, j j w i C(i, j) C(i 1,j)根据动态规划函数，用一个(n 1) (W 1)的二维数组C存放中间变量，C[i][ j]表示把前i个物品装入容量为j 的背包中获得的最大价值。

设物品的重量存放在数组w[n] 中，价值存放在数组v[n] 中，背包的容量为W ，数组C[n 1][W 1]存放迭代的结果，数组x[n] 存放装入背包的物品，动态规划解0-1 背包问题的源代码在文件夹《动态规划法》中。

回溯法分析：用回溯法解0_1 背包问题时，会用到状态空间树。

在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。

当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。

设r 是当前剩余物品价值总和；cp 是当前价值；bestp 是当前最优价值。

当cp+r ≤bestp 时，可剪去右子树。

计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。

由此得到的价值是右子树中解的上界，用此值来剪枝。

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可。

在实现时，由MaxBoundary 函数计算当前结点处的上界。

它是类Knap 的私有成员。

Knap 的其他成员记录了解空间树种的节点信息，以减少函数参数的传递以及递归调用时所需要的栈空间。

在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数MaxBoundary ，以判断是否可以将右子树减去。

进入左子树时不需要计算上界，因为其上界与父结点的上界相同。

在调用函数Knapsack 之前，需要先将各物品依其单位重量价值从达到小排序。

为此目的，我们定义了类Objiect 。

其中，运算符与通常的定义相反，其目的是为了方便调用已有的排序算法。

在通常情况下，排序算法将待排序元素从小到大排序。

在搜索状态空间树时，由函数Backtrack 控制。

在函数中是利用递归调用的方法实现了空间树的搜索。

具体的代码见《回溯法》文件夹。

限界分支法：在解0-1 背包问题的优先队列式界限分支法中，活结点优先队列中结点元素N 的优先级由该结点的上界函数MaxBoundary 计算出的值uprofit 给出。

该上界函数在0-1 背包问题的回溯法总已经说明过了。

子集树中以结点N 为根的子树中任一个结点的价值不超过N.profit 。

因此我们用一个最大堆来实现活结点优先队列。

堆中元素类型为HeapNode,其私有成员有uprofit,profit,weight,level, 和ptr 。