算法分析与设计课程设计论文01背包问题研究及算法策略比较分析.docx

数学与物理科学学院算法分析与设计课程考查论文题目0-1背包问题研究及算法策略比较分析专业班级学号姓名任课教师完成日期2011/5/24摘要背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、OT背包问题及简单o-i背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决OT背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。一、绪论1.1 问题的研究及意义0-1背包问题是计算机科学中的一个非常经典的优化问题。它的主要思路是假定某人拥有大量物品，重量各不同。通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。1.2 0-1背包问题的算法研究与分析0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。OT背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。L3课题的主要研究内容问题的一般描述是：旅行者背包登山，背包的最大承重为M,现有n个物品可供选择装入背包，第i个物品莺量为wi,价值为pi,假定物品i的一部分xi(Oxil)放人背包，获得价值为xipi,由于背包最大承重为M,要求装入物品总质量不过超过M,问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。背包问题的数学描述如下：要求找到一个n元向量(xl,x2-n),在满足约束条件：<Z七",”情况下，使得目标函数maxZQ,其中，lin;M>0；Owl''wi>0；pi>0o满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解O给定11种物品和1个背包。物品i的重量是Wi,其价值为pi,背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品io该问题称为0-1背包问题。OT背包问题的符号化表示是，给定M>0,Wi>0,pi>0,lin,要求找到一个n元OT向量向量(xl,x2xn),Xi=O或1,lin,使得ZXMM,而且Zy达到最大。二、0-1背包问题在动态规划中的实现2.1 动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：分析最优解的结构：最有子结构性质；建立递归方程；计算最优值；构造最优解。2.2 0-1背包问题的实现最优子结构性质OT背包问题具有最优子结构性质。设(yl,y2yn)是所给OT背包问题的一个最优解，则(y2,y3yn)是下面相应子问题的一个最优解：nk=i< h7jJk=ixk0,l,z<k<n因若不然，设(z2,z3Zn)是上述问题的一个最优解，而(y2,y3yn)不是它的最优解，由此可见之>£匕,且wlyl+£吗2,c0因此i=2i=2z=2viyi+v.2.>Z匕i=2z=lwlyl+wzzzcz=2这说明(yl,z2Zn)是所给OT背包问题的一个更优解，从而(yl,y2yn)不是所给OT背包问题的最优解。此为矛盾。递归关系设所给0-1背包问题的子问题nmaxk=i'n< EMXkWjk=jxk0,l,zkn的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为Li+l,n时0-1背包问题的最优值。由OT背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下:maxm(z+1),7),m(+1,7-wz)+vz,7wim(,j)m(+1,7),07<jvnjwm(n,j)=.0j<wn算法描述基于以上讨论，当wi(lin)为正整数时，用二维数组m来存储m(i,j)的相应值，可设计解OT背包问题的动态规划算法Knapsack入下：template<classType>voidKnapsack(Typev,intw,intc,intn,Type*m)intjMax=min(wn-l,c);for(intj=0;j<=jMax;j+)mnj=0;for(intj=wn;j<=c;j+)mnj=vn;for(inti=11-l;i>l;i-)jMax=min(wi-l,c);for(intj=0;j<=jMax;j+)mij=mi+lj;for(intj=wi;j<=c;j+)mij=max(mi+lj,mi+lj-wi+vi);mlc=m2c;if(c>=wl)mlc=max(mlc,m2c-wl+vl);)template<classType>voidTraCebaCk(Type*m,intw,intc,intn,intx)for(inti=l;i<=n;i+)if(mic=mi+lc)xi=0;elsexi=1;c-=wi;xn=(mnc)?l:0;计算复杂性分析利用动态规划求解OT背包问题的复杂度为0(minnc,2n)。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题。三、0-1背包问题在分枝-限界法中的实现3.1 分枝-限界法的基本原理与分析分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点(expansionnode)的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出(最优)可行解的结点，其余结点加人活结点表,然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。有两种常用的方法可用来选择下一个E-结点：先进先出(FIFO)即从活结点表中取出结点的顺序与加人结点的顺序相同，因此活结点表的性质与队列相同。最小耗费或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活结点表可以最小堆来建立，下一个E-结点就是具有最小耗费的活结点，如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个E-结点是具有最大收益的活结点由。3.2 0-1背包问题的实现0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限Upprofit,使得以活结点为根的子树中的任一结点的收益值都不可能超过UPPrOfit,活结点的最大堆使用UPPrOfit作为关键值域。在子集树中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列(即最大堆)，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。则主要算法描述为：classObjectfriendintKnapsack(int*,int*,int,int,int*);public:intoperator<=(Objecta)constreturn(d>=a.d);private:intID;floatd;单位重量价值)；template<classTypew,classTypep>classKnap;classbbnodefriendKnap<int,int>friendintKnapsack(int*,int*,int,int,int*);private:bbnodearent;/指向父结点的指针boolLChild;/左儿子结点标志)；template<classTypew,classTypep>classHeapNodefriendKnap<Typew,Typep>public:operatorTypep()constreturnuprofit;private:Typepuprofit,/结点的价值上界profit;/结点所相应的价值Typewweight;结点所相应的重量intlevel;活结点在子集树中所处的层序号bbnode*ptr;/指向活结点在子集树中相应结点的指针;template<classTypew,classTypep>classKnapfriendTypepKnapsack(TypepTypew*,Typew,int,int*);public:TypepMaxKnapsackO；private:MaxHeap<HeapNode<Typep,TyPeW>*H;TypepBound(inti);voidaddLiveNode(Typepup,Typepcp,Typepcw,boolch,intlevel);bbnode*E;/指向扩展结点的指针Typewc;背包容量intn;/物品总数Typew*w;/物品重量数组Typep*p;/物品价值数组Typewcw;/当前装包重量Typepcp;当前装包价值int*bestx;/最优解)；template<classTypew,classTypep>TypepKnap<Typew,Typep>:MaxKnapsack()/优先队列式分支限界法，返回最大价值，bestx返回最优解/定义最大堆的容量为100OH=newMaxHeap<HeapNode<Typep,Typew>>(1000);/为bestx分配存储空间bestx=newintn+l;inti=l;cw=cp=0;Typepbestp=0;当前最优值Typepup=Bound(I);价值上界while(i!=n+l)/非叶结点TypewWt=cw+wi;if(wt<=c)/左儿子结点为可行结点if(cp+pi>bestp)bestp=cp+pi;AddliveNode(up,cp+pi,cw+wi,ture,i+l);up=Bound(i+l);if(UP>=bestp)右子树可能含最优解AddLiveNode(up,cp,cw,false,i+l);HeapNode<Typep,Typew>N;H->deleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i=N.level;for(intj=n;j>0;j)bestxj=E->LChild;E=E->parent;returncp四、O-L背包问题在遗传算法中的实现4.1遗传算法的基本原理与分析遗传算法可看成是在一个定义域为L维的向量空问Bo中有一适应度函数，依其适应度大小，随机进行选择、交叉和变异操作来求此函数的最大值，即将遗传算法看成是在某个空间进行求最大值的搜索技术。在操作中，新点主要是由交叉操作产生。传统的交叉算子是随机操作，后代简单地继承了“父母”的一部分基因，并不能保证子代的性能优于父辈，而且以这种方式点对点的搜索范围有限，可能会忽略邻域内更好的点而使结果收敛于局部最优。4.20-1背包问题的实现(1)编码方案：用遗传算法来求解OT背包问题，一种很自然的编码方案是将待求解的各量X表示成长为n的二进制字符串Xi,j=l,2,n,xi=l表示物体j放人背包，xj表示物体j放入背包。(2)适应度函数的设计：基于上述编码，按照所提出的罚函数处理约束条件的方法构造背包问题的适应度函数%(X)：L(X)=ZXNY(X)这里，对于所有满足条EJWKC的可行解X,惩罚函数Va(X)=O惩罚函数可以使用对数函数，线性函数，二次函数等，分别随侵犯的程度增加而顺序采用。(3)选择操作：根据选择概率选择染色体，将上述的个体作为第。代。对于每个染色体，计算累积概率Qi,从区间(0,Qi)种产生一个随机数r,若Qi-l<r<Qi,则选择第i个染色体，重复上述操作，复制染色体。(4)交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进行交叉，一般采用单点交叉方式。(5)变异操作：染色体变异采用位点变异的方式。使变异后的适应度至少大于等于原适应度，否则重新选择变异位进行变异，如此重复若干次，若适应度值没有提高，则变异失败。(6)当某代得到的结果满足要求或当前代数等于结束代数时算法结束得到结果，否则重复上述步骤(3)、。则主要算法描述为：proceduresearch(k,v:integer);搜索第k个物品，剩余空间为vvari,j:integer;beginifv<bestthenbest:=v;ifv-(sn-sk-l)>=bestthenexit;sn为前n个物品的重量和ifk<=nthenbeginifv>wkthensearch(k+l,v-wk);search(k+l,v);end;end;1DPFi,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现：A:将最优化问题转化为判定性问题fi,j=fi-l,j-wi(wI<=j<=v)边界：f0,0:=true.For1:=1tondoForj:=wItovdoFI,j:=fI-l,j-wI;优化：当前状态只与前一阶段状态有关，可降至一维。F0:=true;For1:=1tondobeginFl:=f;Forj:=wItovdoIffj-wIthenflj:=true;F:=fl;End;B:求可以放入的最大价值。FI,j为容量为I时取前j个背包所能获得的最大价值。Fi,j=maxfi-wj,jT+pj,fi,jlC:求恰好装满的情况数。DP:Procedureupdate;varj,k:integer;beginc:=a;forj:=0tondoifaj>0thenifj+now<=ntheninc（cj+now,aj）;a:=c;end9;五、O-L背包问题在回溯法中的实现5.1 回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。0溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。使用递归同溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有2"个，因此随着物件数n的增大，其解的空间将以n2"级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。5.2 OT背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到CP(当前节点所获收益)之上，若(r+cp)bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。5.3O-L背包问题在回溯法中的算法描述template<classTypew,classTypep>classKnapfriendTypepKnaPSaCk(TyPeP*,Typew*,Typew,int);private：TypepBound(inti);voidBacktrack(inti);Typewc;/背包容量intn;/物品数Typew*w;/物品重量数组Typep;/物品价值数组Typewcw;/当前重量Typepcp;/当前价值Typepbestp;/当前最优价值)；template<classTypew,classTypep>voidknap<Typew,Typep>:Backtrack(inti)if(i>n)/到达叶结点bestp=cp;return;if(cw+wi<=c)/进入左子数cw+=wi;cp+=pi;Backtrack(i+l);cw-=wi;cp-=pi;if(Bound(i+l)>bestp)/进入右子数Backtrack(i+l);)template<classTypew,classTypep>TypepKnap<Typew,Typep>:Bound(inti)/计算上界Typewcleft=c-cw;/剩余容量Typepb=cp;while(i<=nfefewi<=cleft)cleft-=wi;b+=pi;i+；)if(i<=n)b+=picleftwi;returnb;)classObjectfriendintKnaPSaCk(int*,int*,int,int);public;intoperator<=(Objecta)constreturn(d>=a.d);private:intID;floatd;)；template<classTypew,classTypep>TypepKnapsack(Typepp,Typepw,Typewc,intn)为Knap:Backtrack初始化TypewW=O;TypepP=0;Object*Q=newObjectn;for(inti=l;i<=n;i+)Qi-l.ID=i;Qi-l.d=l.0iwi;p+=pi；w+=wi;)if(w<=c)returnP;/装入所有物品sort(Q,n);Knap<Typew,Typep>K;K.p=newTypepn+l;K.w=newTypewn+1;for(inti=l;i<=n;i+)K.pi=pQi-l.ID;K.wi=wQi-l.ID;)K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;回搠搜索K.Backtrack(I);deleteQ;deleteK.w;deleteK.p;retureK,bestp;15.4算法效率由于计算上界函数需要0(n)时间，在最坏情况下有0(2")个右孩子结点需要上界函数,故计算OT背包问题的回溯算法所需的计算时间复杂度为0(n2")。对回溯法的改进主要是对判断是否移动右子树上，一种更有效的方法是按效益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量,当遇到第一个不能全部放人背包的对象时，就使用它的一部分。回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数，省去许多无谓的搜索，使得搜索速度更快，其调用限界函数计算上界需花费0(n)时间，最坏情况下有0(2")个结点需调用限界函数,需花费0(n)时间,所以该算法的时间复杂度为0(n2")叫回溯法的另一个重要特性就是在搜索执行的同时产生解空间在搜索期间的任何时刻仅保留从开始结点到当前可扩展结点的路径其空间需求为0(从开始结点起最长路径的长度)，所以，此处该算法的空间复杂度为0(n),回溯法是算法设计的基本方法之一，它适用于解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题,且适用于求解组合数量较大的问题。5.5运行结果Cr*E:dddddDebugss.exe*by仲新奎F输入背包容量:)：,输入物品的个数n*,输入物品的价值P：75354请输入物品的重量艰：5?35最优解为bestx):隰忧值为bestp：11010产CsJ重新开始IqJ退出六、四种算法的比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过对0-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算法可读性要优于前者。动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝,常用的分枝一限界法有最小耗费法，最大收益法。FIFo(先进先出)法等。0-1背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要0(2")的解空间。故该算法不常用在背包问题求解。遗传算法是计算数学中用于解决最优化的搜索算法，是一种进化算法。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。通常解用二进制O和1表示，进化从一个个体发生，然后一代一代发生。在每一代中，该种群的价值被评估，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择。回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0（解空间的最大路径长度），而分枝限界所占用的内存为0（解空间大小）。对于一个子集空间，回溯法需要0（n）的内存空间，而分枝限界则需要0（2n）的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。为了更直观更有效地分析动态规划法回溯法两种算法，下面分别对它们的计算时间进行测试。测试中,每个OT背包问题的效益和重量分别为随机产生的两组数据,其取值范围为0,999,背包容量定为1125。为便于各算法间进行比较，测试之前首先把物品按价值重量比的非增顺序排序。每次测试将程序运行100次所得时间为运行100次的平均值。测试结果如下表所示四。问题规模平均计算时间动态规划法回溯法50.0031120.003817100.0093700.009630150.0125500.013120200.0151500.015780250.0171800.018900500.0264600.0267101000.0418700.0398402000.0725500.058430从表中的测试结果可以看出当问题规模较小时，三种方法都有较好的稳定性，计算时间都相差不多。随着问题规模的增大，各算法的计算时间都在增大，其中递归法的计算时间增长速度最快，当问题规模为50,100和200时，其计算时间太长以致失去利用该法求解的意义，而动态规划法与回溯法则相对稳定且计算时间也相差不多，但是当问题规模大到一定程度，回溯法要优于动态规划法。通过以上对OT背包问题的求解分析，我们可以看到各种算法设计方法有各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解OT背包问题，各算法的时问复杂度、优缺点以及改进方法的比较如下表所示加：动态规划0(minnc,2n)可求得最优决策序列速度较慢建立动态规划递归方程回溯法0(n2")能够获得最优解时间复杂度较高判断右子树时，按效率密度vi/wi对剩余对象排序分枝-限界法0(2")速度较快，易求解占用的内存较大，效率不高最大收益或最小消耗分枝-限界法,FIFO法遗传算法0(n2")能够解决传统算法不能解决的问题，能够获得最优解速度较慢，算法不成熟基于惩罚函数修正方法和译码方法七、附录#include<iostream>usingnamespacestd;classKnap(frienditKapsack(itp5itw5itc5it);public:voidprint()(for(itm=1;m<=n;m+)cout<<bestxm<<""cout<<endl;)；private:intBoud(iti);voidBacktrack(inti);intc;背包容量int;物品数int*w;物品重量数组int*p;物品价值数组intcw;当前重量intcp;当前价值intbestp;/当前最优值int*bestx;/当前最优解int*x;当前解)；intKnap:Bound(inti)(intCleft=C-Cw;剩余容量intb=cp;while(i<=n&&wi<=cleft)cleft-=wi;b+=p;i+；if(i<=)b+=piwi*cleft;returnb;)voidKnap:Backtrack(inti)(if(i>)(if(bestp<cp)(for(intj=1J<=J+)bestxj=xj;bestp=cp;return;)if(cw+wi<=c)搜索左子树(×i=1;cw+=wi;cp+=Pi;Backtrack(i+1);cw-=wi;CP-=P;讦(BOUnd(i+1)>bestp)搜索右子树xi=0;Backtrack(i+1);classObject(frienditKapsack(itp5itw5itc5it);public:intoperator<=(Objecta)cost(return(d>=a.d);private:intID;floatd;)；intKnapsack(intp5intw5intc5int)(为KnaP:BaCktraCk初始化intW=0;intP=0;inti=1;Object*Q=newObject;for(i=1;i<=n;i+)(Qi-1.ID=i;Qi-1.d=1.0*piwi;P÷=pi;W+=wi;if(W<=c)returnP;装入所有物品floatf;for(i=0;i<n;i+)for(intj=i;j<n;j+)(if(Qi.d<Qj.d)(f=Qi.d;Qi.d=Qj.d;Qj.d=f;)KnapK;K.p=newintn+1;K.w=newit+1;K.x=newintn+1;K.bestx=newintn+1;K.x0=0;K.bestx0=0;for(i=1;i<=n;i+)(K.pi=pQi-1.ID;K.wi=wQi-1.ID;)K.cp=0;K.cw=0;K.c=c;K.=;K.bestp=O;回溯搜索K.Backtrack(I);K.prit();deleteQ;deleteK.w;deleteK.p;returnK.bestp;voidmai()(int*p;int*w;intc=0;int=0;inti=0;chark;cout<<"0-1背包问题回溯法"<<edl;cout<<"by仲新奎11<<edl;while(k)(COUtVV”请输入背包容量(c)：”VVendI;cin>>c;CoUtVV”请输入物品的个数(n)：”VVendI;ci>>p=ewitn+1;w=ewit+1;p0=0;w0=0;CoLltVV”请输入物品的价值(p)：”VVendI;for(i=1;i<=n;i+)ci>>pi;CoLltVV”请输入物品的重量(W):“VVendI;for(i=1;i<=n;i+)ci>>wi;COUtVV”最优解为(bestx)："<<edl;CoUtVV”最优值为(bestp)："<<edl;cout<<Kapsack(p5w5c5n)<<edl;cout<<"s重f开始"VVendI;cout<<"q退出"VVendI;cin>>k;