回溯法和分支限界法解决0~1背包题

1、0-1背包问题计科1班朱润华 2012040732方法1 :回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个(最优)解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有 0-1 赋值。例如 n=3 时，解空间为：( 0, 0 , 0), (0 , 1, 0 ), (0 , 0 , 1) , (1, 0 ,0), (0 , 1 , 1), (1 , 0, 1 ), (1 , 1 , 0), (1 , 1 , 1)然后可将解空间组织成树或图的 形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是

2、wi，其价值为vi，背包的容量为 C。问:应如何选择装入背包的物品，使得装入背包中物品 的总价值最大？形式化描述：给定 c 0, wi 0, vi 0 , 1wiwn要求找一 n元向量(x1,x2,xn,), xi 0,1, ?刀wi xi wc,且刀vi xi达最大即一个特殊的整数规划问题。二、回溯法步骤思想描述：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当 c

3、p+r=bestp 时，可剪去右子树。计算右子树上界 的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。例如：对于0-1背包问题的一个实例，n=4,c=7,p=9,10,7,4,w=3,5,2,1 。这4个物品的单位重量价值分别为3,2,3,5,4。以物品单位重量价值的递减序装入物品。先装入物品 4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为1,0.2,1,1，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。在实现时，由Bou

4、nd计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。三、回溯法实现代码：#include stdafx.h#in clude using n amespace std;templateclass Knaptemplatefriend Typep Kn apsack(Typep ,Typew ,Typew,i nt);private:Typep Boun d(i nt i);void Backt

5、rack(i nt i);Typew c;/背包容量int n;/物品数Typew *w;/物品重量数组Typep *p;/物品价值数组Typew cw;/当前重量Typep cp;/当前价值Typep bestp;/ 当前最后价值;templateTypep Kn apsack(Typep p,Typew w,Typew c,i nt n); template in li ne void Swap(Type &a,Type &b);templatevoid BubbleSort(Type a,int n);int mai n()intn = 4;/物品数int c = 7;/ 背包容量in

6、t p = 0,9,10,7,4;/ 物品价值 下标从1开始int w = 0,3,5,2,1;物品重量 下标从1开始cout背包容量为：ce ndl;cout物品重量和价值分别为：e ndl;for(i nt i=1; i=n; i+)cout(wi,pi);coute ndl;cout背包能装下的最大价值为：K napsack(p,w ,c,n )e ndl;return 0;templatevoid Kn ap:Backtrack(i nt i)if(i n)到达叶子节点bestp = cp;return;if(cw + wi bestp) 进入右子树Backtrack(i+1);tem

7、plate计算上界Typep Kn ap:Bo un d(i nt i)/Typew cleft = c - cw; / 剩余容量Typep b = cp;/以物品单位重量价值递减序装入物品while (i = n & wi = cleft)cleft -= wi;b += pi;i+;/装满背包if (i = n)b += pi/wi * cleft;return b;class Objecttemplatefriend Typep Kn apsack(Typep,Typew ,Typew,i nt); public:int operator =a.d);private:int ID;float d;templateTypep Kn apsack(Typep p,Typew w,Typew c,i nt n) / 为 Knap:Backtrack 初始化Typew W = 0;Typep P = 0;Object *Q = new Object n;for(i nt