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

《回溯法、分支限界法解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;i

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