欢迎来到天天文库
浏览记录
ID:60826045
大小:154.00 KB
页数:15页
时间:2020-12-20
《回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告).doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、实验报告课程名称:算法设计与分析实验名称:回溯法、分支限界法解0-1背包问题任课教师:张锦雄专业:计算机科学与技术班级:2007级1班学号:姓名:蓝冠恒完成日期:2011年1月12日一、实验目的:掌握回溯法、分支限界法的原理,并能够按其原理编程实现解决0-1背包问题,以加深对回溯法、分支限界法的理解。二、主要实验内容及要求:1.要求分别用回溯法和分支限界法求解0-1背包问题;2.要求交互输入背包容量,物品重量数组,物品价值数组;3.要求显示结果。三、实验环境和工具:操作系统:win7操作系统开发工具:eclipse3.4、jdk1.6开发语言:java四、实验结果与结论:(经调试
2、正确的源程序和程序的运行结果)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;//当前重量double
3、cp;//当前价值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;i4、ewElemComparator());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(i>n){//达到叶节点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)>bes5、tp){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;//单位重量价值publicE6、lement(intid,doubled){this.id=id;this.d=d;}}/***比较器*@author蓝冠恒*/publicclassElemComparatorimplementsComparator{publicintcompare(Objectobject1,Objectobject2){Elementelement1=(Element)object1;Elementelement2=(Element)object2;if(element1.d7、voidmain(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("请选择数字功
4、ewElemComparator());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(i>n){//达到叶节点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)>bes
5、tp){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;//单位重量价值publicE
6、lement(intid,doubled){this.id=id;this.d=d;}}/***比较器*@author蓝冠恒*/publicclassElemComparatorimplementsComparator{publicintcompare(Objectobject1,Objectobject2){Elementelement1=(Element)object1;Elementelement2=(Element)object2;if(element1.d7、voidmain(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("请选择数字功
7、voidmain(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("请选择数字功
此文档下载收益归作者所有