装载问题的回溯算法实现.doc

《装载问题的回溯算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《装载问题的回溯算法实现》实验报告一、实验目的通过本实验使学生掌握回溯算法基本要素、步骤及其应用二、实验原理本实验是应用回溯算法用Java编程语言对给定两艘轮船的载重量和一批集装箱，集装箱的重量之和小于等于两艘船的载重量之和。Java编程语言见《Java基础教程》,装载问题的回溯算法见王晓东编《算法设计与分析（第二版）》p152-160.三、实验内容Java编程语言实现装载问题的回溯算法。主要实验内容包含：给定两艘轮船的载重量c1和c2，n个集装箱及其重量w[n]，确定合理的装载方案将n个集装箱装上这两艘船。四、使用仪

2、器、材料myEclipse五、实验步骤1、给定轮船的载重量c1和c2，集装箱数量n和集装箱重量的集合w[n]；2、用回溯算法将第一艘轮船尽可能装满；3、输出第一艘轮船的装载方案；4、输出第二艘船的装载方案。六、实验原始记录及其处理（数据、图表、计算等）packagets;publicclassLoad{staticintn;staticint[]w={40,50,40,30,55};//第一个并没有使用//staticint[]ww;staticintc1,c2;staticintcw;staticintbestw;s

3、taticintr;staticint[]x;//staticint[]y;staticint[]bestx;publicstaticintmaxLoading(int[]w,intcc,int[]xx){n=w.length-1;cw=0;bestw=0;bestx=xx;for(inti=0;i<=n;i++){r+=w[i];}backtrack(1,cc);returnbestw;}publicstaticvoidbacktrack(inti,intcc){//搜索第i层结点if(i>n)//到达叶结点{if(

4、cw>bestw){for(intj=1;j<=n;j++)bestx[j]=x[j];//更新最优解bestxbestw=cw;//更新最优值bestw}return;}r-=w[i];if(cw+w[i]<=cc){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1,cc);cw-=w[i];}if(cw+r>bestw){x[i]=0;//搜索右子树backtrack(i+1,cc);}r+=w[i];}publicstaticvoidmain(String[]args){intk=1;//

5、intj=0;c1=110;c2=100;x=newint[w.length];maxLoading(w,c1,x);for(inti=1;i

6、ww=newint[k];//for(inti=0;i

7、果如下：主要步骤是用回溯法找出装入1船的最优装载方案，然后把剩下的货物一次装入2船中。注：w.length=5,但是在程序运行时是从w[1]开始的，所以w[0]，没有用，输出时只有四个集装箱。