回溯法和分支限界法解决0-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的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c0,wi0,vi0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},?∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。二、回溯法步骤思想描述：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+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。在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。三、回溯法实现代码：#includestdafx.h#includeiostreamusingnamespacestd;templateclassTypew,classTypepclassKnap{templateclassTypew,classTypepfriendTypepKnapsack(Typep[],Typew[],Typew,int);private:TypepBound(inti);voidBacktrack(inti);Typewc;//背包容量intn;//物品数Typew*w;//物品重量数组Typep*p;//物品价值数组Typewcw;//当前重量Typepcp;//当前价值Typepbestp;//当前最后价值};templateclassTypew,classTypepTypepKnapsack(Typepp[],Typeww[],Typewc,intn);templateclassTypeinlinevoidSwap(Type&a,Type&b);templateclassTypevoidBubbleSort(Typea[],intn);intmain(){intn=4;//物品数intc=7;//背包容量intp[]={0,9,10,7,4};//物品价值下标从1开始intw[]={0,3,5,2,1};//物品重量下标从1开始cout背包容量为：cendl;cout物品重量和价值分别为：endl;for(inti=1;i=n;i++){cout(w[i],p[i]);}coutendl;cout背包能装下的最大价值为：Knapsack(p,w,c,n)endl;return0;}templateclassTypew,classTypepvoidKnapTypew,Typep::Backtrack(inti){if(in)//到达叶子节点{bestp=cp;return;}if(cw+w[i]=c)//进入左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)bestp)//进入右子树{Backtrack(i+1);}}templateclassTypew,classTypepTypepKnapTypew,Typep::Bound(inti)//计算上界{Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i=n&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i=n){b+=p[i]/w[i]*cleft;}returnb;}classObject{templateclassTypew,classTypepfriendTypepKnapsack(Typep[],Typew[],Typew,int);public:intoperator=(Objecta)const{return(d=a.d);}private:intID;floatd;};templateclassTypew,classTypepTypepKnapsack(Typepp[],Typeww[],Typewc,intn){//为Knap::Backtrack初始化TypewW=0;TypepP=0;Object*Q=newObject[n];for(inti=1;i=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W=c)//装入所有物品{returnP;}//依物品单位重量价值排序BubbleSort(Q,n);KnapTypew,TypepK;K.p=newTypep[n+1];K.w=newTypew[n+1];for(inti=1;i=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}templateclassTypevoidBubbleSort(Typea[],intn){//记录一次遍历中是否有元素的交换boolexchange;for(inti=0;in-1;i++){exchange=false;for(intj=i+1;j=n-1;j++){if(a[j]=a[j-1]){Swap(a[j],a[j-1]);exchange=true;}}//如果这次遍历没有元素的交换,那么排序结束if(false==exchange){break;}}}templateclassTypeinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}四、程序运行结果：五、回溯法解决0-1背包问题复杂度分析：计算上界需要O(n)时间，在最坏情况下有O(2^n)个右儿子节点需要计算上界，故解0-1背包问题的回溯算法所需要的计算时间为O(n2^n)。方法2：分支限界法：一、分支限界法描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c0,wi0,vi0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。二、分支限界法步骤思想：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。例如：0-1背包问题，当n=3时，w={16,15,15},p={45,25,25},c=30。优先队列式分支限界法：处理法则:价值大者优先。{}—{A}—{B,C}—{C，D，E}—{C，E}—{C，J，K}—{C}—{F，G}—{G，L，M}—{G，M}—{G}—{N，O}—{O}—{}。三、分支限界法解决0-1背包问题实现代码：//0-1背包问题分支限界法求解#includestdafx.h#includeMaxHeap.h#includeiostreamusingnamespacestd;classObject{templateclassTypew,classTypepfriendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);public:intoperator=(Objecta)const{returnd=a.d;}private:intID;floatd;//单位重量价值};templateclassTypew,classTypepclassKnap;classbbnode{friendKnapint,int;templateclassTypew,classTypepfriendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);private:bbnode*parent;//指向父节点的指针boolLChild;//左儿子节点标识};templateclassTypew,classTypepclassHeapNode{friendKnapTypew,Typep;public:operatorTypep()const{returnuprofit;}private:Typepuprofit,//节点的价值上界profit;//节点所相应的价值Typewweight;//节点所相应的重量intlevel;//活节点在子集树中所处的层序号bbnode*ptr;//指向活节点在子集中相应节点的指针};templateclassTypew,classTypepclassKnap{templateclassTypew,classTypepfriendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);public:TypepMaxKnapsack();private:MaxHeapHeapNodeTypep,Typew*H;TypepBound(inti);voidAddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev);bbnode*E;//指向扩展节点的指针Typewc;//背包容量intn;//物品数Typew*w;//物品重量数组Typep*p;//物品价值数组Typewcw;//当前重量Typepcp;//当前价值int*bestx;//最优解};templateclassTypeinlinevoidSwap(Type&a,Type&b);te