回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告)

实验报告课程名称：算法设计与分析实验名称：回溯法、分支限界法解0-1背包问题任课教师：张锦雄专业：计算机科学与技术班级:2007级1班学号：姓名：蓝冠恒完成日期：2011年1月12日一、实验目的：掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。二、主要实验内容及要求：1．要求分别用回溯法和分支限界法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。三、实验环境和工具：操作系统:win7操作系统开发工具：eclipse3.4、jdk1.6开发语言：java四、实验结果与结论：（经调试正确的源程序和程序的运行结果）1.1、回溯法求解0-1背包问题源代码：packagecn.lgh;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Arrays;importjava.util.Comparator;/***回溯法解0-1背包问题。*@author蓝冠恒*/publicclassBTKnapsack{doublec;//背包重量intn;//物品总数double[]w;//物品重量数组double[]p;//物品价值数组doublecw;//当前重量doublecp;//当前价值doublebestp;//当前最优价值/***回溯法解0-1背包问题。*@parampp*物品价值数组*@paramww*物品重量数组*@paramcc*背包重量*@return最优价值*/publicdoubleknapsack(doublepp[],doubleww[],doublecc){c=cc;n=pp.length;cw=0.0;cp=0.0;bestp=0.0;Element[]q=newElement[n];for(inti=0;in;i++){q[i]=newElement(i+1,pp[i]/ww[i]);}Arrays.sort(q,newElemComparator());p=newdouble[n+1];w=newdouble[n+1];for(inti=1;i=n;i++){p[i]=pp[q[i-1].id-1];w[i]=ww[q[i-1].id-1];}backtrack(1);returnbestp;}//回溯过程privatevoidbacktrack(inti){if(in){//达到叶节点bestp=cp;return;}if(cw+w[i]=c){cw+=w[i];cp+=p[i];backtrack(1+i);cw-=w[i];cp-=p[i];}if(bound(i+1)bestp){backtrack(1+i);}}//计算上界值privatedoublebound(inti){doublecleft=c-cw;doublebound=cp;//以物品单位重量价值递减顺序装入物品while(i=n&&w[i]=cleft){cleft-=w[i];bound+=p[i];i++;}//装满背包if(i=n){bound+=p[i]*cleft/w[i];}returnbound;}/***物体编号和单位重量价值载体。*@author蓝冠恒*/publicclassElement{intid;//编号doubled;//单位重量价值publicElement(intid,doubled){this.id=id;this.d=d;}}/***比较器*@author蓝冠恒*/publicclassElemComparatorimplementsComparatorObject{publicintcompare(Objectobject1,Objectobject2){Elementelement1=(Element)object1;Elementelement2=(Element)object2;if(element1.delement2.d){return1;}else{return0;}}}publicstaticvoidmain(String[]args){Stringinput;Stringflag;doublecapacity=0;double[]pp;double[]ww;doublebestP=0.0;BTKnapsackbtKnapsack=newBTKnapsack();BufferedReaderin=newBufferedReader(newInputStreamReader(System.in));do{try{do{System.out.println(请选择数字功能键：1--输入数据，2--退出系统);flag=in.readLine().trim();}while(!(flag.equals(1)||flag.equals(2)));if(flag.equals(2)){break;}do{System.out.println(请输入各物品重量，数据之间必须以顿号间隔分开！);input=in.readLine().trim();input=in.readLine().replaceAll(,);}while(input.equals());if(input.equals(2)){break;}Stringdatas[]=input.split([、]);intn1=datas.length;pp=newdouble[n1];ww=newdouble[n1];for(inti=0;in1;i++){ww[i]=Double.parseDouble(datas[i]);}do{System.out.println(请输入各物品价值，数据之间必须以顿号间隔分开！);input=in.readLine().trim();input=in.readLine().replaceAll(,);}while(input.equals());if(input.equals(2)){break;}datas=input.split([、]);intn2=datas.length;if(n1!=n2){System.out.println(输入数据个数不一致，重新输入);continue;}for(inti=0;in1;i++){pp[i]=Double.parseDouble(datas[i]);}do{System.out.println(请输入背包的容量：);input=in.readLine().trim();input=in.readLine().replaceAll(,);}while(input.equals());if(input.equals(2)){break;}capacity=Double.parseDouble(input);bestP=btKnapsack.knapsack(pp,ww,capacity);System.out.println(回溯法解得最优价值：+bestP);}catch(Exceptione){e.printStackTrace();}}while(true);}}1.2、运行结果：2.1、分支限界法求解0-1背包问题源代码：packagecn.lgh;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Arrays;/***分支界限法解0-1背包问题。*@author蓝冠恒*/publicclassBBKnapsack{doublec;//背包重量intn;//物品总数double[]w;//物品重量数组double[]p;//物品价值数组doublecw;//当前重量doublecp;//当前价值int[]bestx;//最优解MaxHeapmaxHeap=newMaxHeap();//活节点优先队列//计算节点所对应的节点的上界privatedoublebound(inti){doublecleft=c-cw;doubleb=cp;//以物品单位重量价值递减装填剩余容量while(i=n&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}//装填剩余容量装满背包if(i=n){b+=p[i]/w[i]*cleft;}returnb;}//添加新的活节点到子集树和优先队列中privatevoidaddLiveNode(doubleupperProfit,doublepp,doubleww,intlevel,BBnodeparent,booleanleftChild){BBnodeb=newBBnode(parent,leftChild);HeapNodenode=newHeapNode(b,upperProfit,pp,ww,level);maxHeap.put(node);}//优先队列式分支界限法privatedoublebbKnapsack(){BBnodeenode=null;inti=1;doublebestp=0.0;doubleup=bound(1);while(i!=n+1){doublewt=cw+w[i];//检查当前扩展节点的左儿子节点if(wt=c){if(cp+p[i]bestp){bestp=cp+p[i];}addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);//检查当前扩展节点的右儿子节点if(up=bestp){addLiveNode(up,cp,cw,i+1,enode,false);}HeapNodenode=maxHeap.removeMax();enode=node.liveNode;cw=node.weight;cp=node.profit;up=node.upperProfit;i=node.level;}//构造当前最优解for(intj=n;j0;j--){bestx[j]=(enode.leftChild)?1:0;enode=enode.parent;}returncp;}/***将个物体依其单位重量价值从大到小排列，然后调用bbKnapsack完成对子集树优先队列式分支界*限搜索。**@return最优解*/publicdoubleknapsack(double[]pp,double[]ww,doublecc,int[]xx){c=cc;n=pp.length;Element[]q=newElement[n];doublews=0.0;doubleps=0.0;for(inti=0;in;i++){q[i]=newElement(i+1,pp[i]/ww[i]);ps+=pp[i];ws+=ww[i];}if(ws=c){for(inti=1;i=n;i++){xx[i]=1;}returnps;}//依单位重量价值排序Arrays.sort(q,newElemComparator());p=newdouble[n+1];w=newdouble[n+1];for(inti=1;i=n;i++){p[i]=pp[q[i-1].id-1];w[i]=ww[q[i-1].id-1];}cw=0.0;cp=0.0;bestx=newint[n+1];maxHeap=newMaxHeap();//调用bbKnapsack求问题的最优解doublemaxp=bbKnapsack();for(inti=1;i=n;i++){xx[q[i-1].id-1]=bestx[i];}returnmaxp;}publicstaticvoidmain(Stringarg[]){Stringinput;Stringflag;doublecapacity=0;do