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

装载问题的回溯算法实现.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]，没有用，输出时只有四个集装箱。