优先队列式分支限界法求解0-1背包问题

算法分析与设计实验报告第7次实验姓名学号班级时间6.4上午地点四合院实验名称优先队列式分支限界法求解0-1背包问题实验目的通过上机实验，要求掌握优先队列式分支限界法求解0-1背包问题的问题描述、算法设计思想、程序设计。实验原理1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树，对于0-1背包问题的解空间树是一个棵子集树。3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩展结点，一旦成为扩展结点就一次性产生所有儿子结点，在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。4、为了尽快找到0-1背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中选择活结点的上界，最大的活结点成为当前的扩展结点。这一过程一直持续到找到所需的解或活结点表为空时为止。实验步骤1、定义树结点类bbnode，用于构造子集树，以便计算最优解；定义堆结点类HeapNode，用于定义堆元素类型；定义最大堆类MaxHeap，用于实现优先队列定义.物品类Object，用于保存物品编号和物品的单位重量价值；定义解决0-1背包问题的主类Knap。2、设计求解0-1背包问题的主函数Knapsack，在其中对物品以单位价值量排序。3、设计负责求解0-1背包问题的最优值和最优解函数MaxKnapsack在其中调用计算结点价值上界函数Bound，向子集树和最大堆中插入结点函数AddLiveNode和释放最大堆最大结点的函数DeleteMax，实现优先级队列。4、输入数据到input.txt文件中。5、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到output文件中。6、分析时间复杂度：在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数时间。但分支限界法本质上还是穷举法，平均时间复杂度仍是指数阶。关键代码//物品类classObject{friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);public:intoperator=(Objecta)const{return(d=a.d);}private:intID;//物品编号floatd;//单位重量价值};//树结点类classbbnode{friendclassKnap;friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);private:bbnode*parent;//指向父节点的指针intLChild;};//堆结点类classHeapNode{friendclassKnap;friendclassMaxHeap;public:operatorTypep()const{returnuprofit;};private:Typepuprofit,//结点的价值上界profit;//结点所相应的价值Typewweight;//结点所相应的重量intlevel;//活结点在子集树中所处的层序号bbnode*elemPtr;//指向该活结点在子集树中相应结点的指针};//最大堆类classMaxHeap{public:MaxHeap(intmaxElem){HeapElem=newHeapNode*[maxElem+1];//下标为0的保留capacity=maxElem;size=0;}voidInsertMax(HeapNode*newNode);HeapNodeDeleteMax(HeapNode*&N);private:intcapacity;intsize;HeapNode**HeapElem;};//0-1背包问题的主类classKnap{friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);public:TypepMaxKnapsack();private:MaxHeap*H;TypepBound(inti);voidAddLiveNode(Typepup,Typepcp,Typewcw,intch,intlevel);bbnode*E;//指向扩展结点的指针Typewc;//背包容量intn;//物品总数Typew*w;//物品重量数组（以单位重量价值降序）Typep*p;//物品价值数组（以单位重量价值降序）Typewcw;//当前装包重量Typepcp;//当前装包价值int*bestx;//最优解};voidMaxHeap::InsertMax(HeapNode*newNode){inti=1;for(i=++size;i/20&&HeapElem[i/2]-uprofitnewNode-uprofit;i/=2){HeapElem[i]=HeapElem[i/2];}HeapElem[i]=newNode;}HeapNodeMaxHeap::DeleteMax(HeapNode*&N){if(size0){N=HeapElem[1];inti=1;while(isize){if(((i*2+1)=size)&&HeapElem[i*2]-uprofitHeapElem[i*2+1]-uprofit){HeapElem[i]=HeapElem[i*2];i=i*2;}else{if(i*2=size){HeapElem[i]=HeapElem[i*2];i=i*2;}elsebreak;}}if(isize)HeapElem[i]=HeapElem[size];}size--;return*N;}TypepKnap::MaxKnapsack(){H=newMaxHeap(10000);bestx=newint[n+1];inti=1;E=0;cw=0;cp=0;Typepbestp=0;Typepup=Bound(1);while(i!=n+1){Typewwt=cw+w[i];if(wt=c){if(cp+p[i]bestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],1,i);}up=Bound(i+1);if(up=bestp)AddLiveNode(up,cp,cw,0,i);HeapNode*N;H-DeleteMax(N);E=N-elemPtr;cw=N-weight;cp=N-profit;up=N-uprofit;i=N-level+1;}for(inti=n;i0;i--){bestx[i]=E-LChild;E=E-parent;}returncp;}TypepKnap::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;}voidKnap::AddLiveNode(Typepup,Typepcp,Typewcw,intch,intlevel){bbnode*b=newbbnode;b-parent=E;b-LChild=ch;HeapNode*N=newHeapNode;N-uprofit=up;N-profit=cp;N-weight=cw;N-level=level;N-elemPtr=b;H-InsertMax(N);}//Knapsack返回最大价值，最优值保存在bestxTypepKnapsack(Typew*w,Typep*p,Typewc,intn,int*bestx){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){for(inti=1;i=n;i++){bestx[i]=p[i];}returnP;}for(inti=1;in;i++)for(intj=1;j=n-i;j++){if(Q[j-1].dQ[j].d){Objecttemp=Q[j-1];Q[j-1]=Q[j];Q[j]=temp;}}KnapK;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;Typepbestp=K.MaxKnapsack();for(inti=1;i=n;i++){bestx[Q[i-1].ID]=K.bestx[i];}delete[]Q;delete[]K.w;delete[]K.p;delete[]K.bestx;delete[]K.H;returnbestp;}测试结果1、测试自己输入的小规模数据2、测试随机生成1003、随机生成1000数据4、随机生成1000数据实验心得在做本次实验之前，我对分支限界法的原理并不是很理解，经过查看课件及网上查找资料，同时结合自己对回溯法等的理解，我对分支限界法有了一个较好的理解，知道了两种主要的分支限界法及分支限界法如何应用于解01背包问题。在查找资料的过程中，我查看了许多网上的别人的代码实现，结合课本上的代码完成了该实验。通过本次试验，我基本上掌握了优先队列分支限界法解0-1背包问题的原理，同时锻炼了自己动手编写及调试代码的能力，收获附录：完整代码#includeiostream#includetime.h#includealgorithm#includefstreamusingnamespacestd;ifstreamin(input.txt);ofstreamout(output.txt);typedefintTypew;typedefintTypep;//物品类classObject{friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);public:intoperator=(Objecta)const{return(d=a.d);}private:intID;//物品编号floatd;//单位重量价值};//树结点类classbbnode{friendclassKnap;friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);private:bbnode*parent;//指向父节点的指针intLChild;};//堆结点类classHeapNode{friendclassKnap;friendclassMaxHeap;良多。实验得分助教签名public:operatorTypep()const{returnuprofit;};private:Typepuprofit,//结点的价值上界profit;//结点所相应的价值Typewweight;//结点所相应的重量intlevel;//活结点在子集树中所处的层序号bbnode*elemPtr;//指向该活结点在子集树中相应结点的指针};//最大堆类classMaxHeap{public:MaxHeap(intmaxElem){HeapElem=newHeapNode*[maxElem+1];//下标为0的保留capacity=maxElem;size=0;}voidIns