装载问题的回溯算法实现.doc
- 文档编号:2149164
- 上传时间:2023-05-02
- 格式:DOC
- 页数:3
- 大小:61.50KB
装载问题的回溯算法实现.doc
《装载问题的回溯算法实现.doc》由会员分享,可在线阅读,更多相关《装载问题的回溯算法实现.doc(3页珍藏版)》请在冰点文库上搜索。
《装载问题的回溯算法实现》实验报告
一、实验目的
通过本实验使学生掌握回溯算法基本要素、步骤及其应用
二、实验原理
本实验是应用回溯算法用Java编程语言对给定两艘轮船的载重量和一批集装箱,集装箱的重量之和小于等于两艘船的载重量之和。
Java编程语言见《Java基础教程》,装载问题的回溯算法见王晓东编《算法设计与分析(第二版)》p152-160.
三、实验内容
Java编程语言实现装载问题的回溯算法。
主要实验内容包含:
给定两艘轮船的载重量c1和c2,n个集装箱及其重量w[n],确定合理的装载方案将n个集装箱装上这两艘船。
四、使用仪器、材料
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;
staticintr;
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(cw>bestw){
for(intj=1;j<=n;j++)
bestx[j]=x[j];//更新最优解bestx
bestw=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;
// intj=0;
c1=110;
c2=100;
x=newint[w.length];
maxLoading(w,c1,x);
for(inti=1;i if(x[i]==1) System.out.println("第"+(i)+"箱货物在第一次装入,装入顺序为"+(k++)); } for(inti=1;i if(x[i]==0) System.out.println("第"+(i)+"箱货物在第二次装入,装入顺序为"+(k++)); } //ww=newint[k]; //for(inti=0;i //if(x[i]==0) //ww[j++]=w[i]; //System.out.println(x[i]); //} //y=newint[k]; //for(inti=0;i //if(x[i]==0)y[i]=x[i]; //} //System.out.println(y.length); //maxLoading(ww,c2,y); } } 七、实验结果及分析 输入的信息如下: 包括集装箱的重量w,1船2船的载重量c1,c2。 输出的结果如下: 主要步骤是用回溯法找出装入1船的最优装载方案,然后把剩下的货物一次装入2船中。 注: w.length=5,但是在程序运行时是从w[1]开始的,所以w[0],没有用,输出时只有四个集装箱。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 装载 问题 回溯 算法 实现