回溯算法装载问题文档格式.docx
- 文档编号:8319244
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:9
- 大小:18.89KB
回溯算法装载问题文档格式.docx
《回溯算法装载问题文档格式.docx》由会员分享,可在线阅读,更多相关《回溯算法装载问题文档格式.docx(9页珍藏版)》请在冰点文库上搜索。
bestw){
x[i]=0;
//搜索右子树
r+=w[i];
4、实验代码
方法1:
importjava.util.*;
/**
*回溯法解决装载问题
*@authorAdministrator
*
*/
publicclassdemo{
publicstaticintn;
//集装箱数
publicstaticintfirst_weight;
//第一艘载重量
publicstaticintbeautif_weight;
//当前最优载重量
publicstaticint[]arr_weight;
//集装箱重量数组
publicstaticint[]xx;
//
publicstaticint[]bestxx;
publicstaticintmaxLoadingRE(int[]w,intc,int[]bestx){//递归回溯
n=w.length;
first_weight=c;
beautif_weight=0;
arr_weight=w;
bestxx=bestx;
xx=newint[n];
intr=0;
//剩余集装箱重量,未进行装载的重量
for(inti=0;
i<
n;
i++){
r+=arr_weight[i];
trackback(0,0,r);
returnbeautif_weight;
//到达层数,目前装载的重量,未装载的重量
privatestaticvoidtrackback(inti,intcw,intr){
if(i==n){//到达叶结点
for(intj=0;
j<
j++){
bestxx[j]=xx[j];
beautif_weight=cw;
return;
//只是一次出栈操作,栈非空还要继续执行
if(cw+arr_weight[i]<
=first_weight){//已装载的加上要装载的小于第一个的载重量
xx[i]=0;
//0代表装在第一个上,1代表装在第二个上
trackback(i+1,cw+arr_weight[i],r);
//试图装载下一个集装箱,r是针对第一个装的重量,因此装在第一个里不需要减,但装在第二个时就要减去该重量
if(r-arr_weight[i]>
beautif_weight){//已装载的加上要装载的已经大于第一个的载重量,并且用总的载重量r减去当前要装载的还比最好的载重量大
xx[i]=1;
//放到第二个上
trackback(i+1,cw,r-arr_weight[i]);
publicstaticintmaxLoading(int[]w,intc,int[]bestx){
inti=0;
//当前层
intn=w.length;
//层总数
int[]x=newint[n];
//x[0,i]为当前选择路径
Arrays.fill(x,-1);
//初始化为-1,0表示选择第一个,1表示选择第二个
intbestw=0;
//当前最优装载重量
int[]cw=newint[n];
//当前载重量
int[]r=newint[n];
//剩余集装箱容量
inttor=0;
for(intitem:
w){//item取出w中的值,进行相加
tor+=item;
r[0]=tor;
//要装载的重量
cw[0]=0;
//搜索子树
while(i>
-1){
do{
x[i]+=1;
if(x[i]==0){//选择放在第一个(左子树)
if(cw[i]+w[i]<
=c){
if(i<
n-1){
cw[i+1]=cw[i]+w[i];
r[i+1]=r[i];
break;
//能放下就直接跳出这个do-while循环
else{//选择放在第二个(右子树)
if(r[i]-w[i]>
bestw){
//剪枝函数,没有最优解好的话x[i]会自增到2,不会进入下面的if(x[i]<
2)
r[i+1]=r[i]-w[i];
cw[i+1]=cw[i];
}while(x[i]<
2);
//对于放不下的在这里判断后才能取右子树
if(x[i]<
2){
if(i==n-1){
bestx[j]=x[j];
if(x[i]==0){
bestw=cw[i]+w[i];
else{
bestw=cw[i];
}
i++;
x[i]=-1;
else{//当x[i]=2时,说明已经遍历完两个叶节点,应向上一层继续遍历其它节点
i--;
returnbestw;
}
publicstaticvoidmain(String[]args){
int[]w={0,10,40,40};
intc=50;
int[]bestx=newint[n];
System.out.println("
重量分别为:
"
);
for(intws:
w){
System.out.print("
"
+ws);
\n"
intbestw=maxLoadingRE(w,c,bestx);
回溯选择结果为:
"
+bestw);
System.out.println(Arrays.toString(bestx));
方法2:
publicclassdemo2{
intn=3,m;
intc=50,c2=50;
intw[]={0,10,40,40};
intbestx[]=newint[w.length];
demo2demo2=newdemo2();
m=demo2.MaxLoading(w,c,n,bestx);
轮船的载重量分别为:
System.out.println("
c
(1)="
+c+"
c
(2)="
+c2);
待装集装箱重量分别为:
System.out.print("
w(i)="
for(inti=0;
i<
=n;
i++)
{
System.out.print("
,"
+w[i]);
}
最优装载量为:
m
(1)="
+m);
x(i)="
+bestx[i]);
intm2=0;
for(intj=1;
j<
j++)
m2=m2+w[j]*(1-bestx[j]);
+m2);
if(m2>
c2)
System.out.println("
因为m
(2)大于c
(2),所以原问题无解!
intMaxLoading(intw[],intc,intn,intbestx[])//迭代回溯法,返回最优载重量及其相应解,初始化根结点
{
inti=1;
//当前层,x[1:
i-1]为当前路径
intx[]=newint[n+1];
intbestw=0;
intcw=0;
intr=0;
//剩余集装箱重量
r+=w[j];
while(true)//搜索子树
{
while(i<
=n&
&
cw+w[i]<
=c)//进入左子树
{
r-=w[i];
cw+=w[i];
x[i]=1;
i++;
}
if(i>
n)//到达叶结点
{
for(intj=1;
{
bestx[j]=x[j];
}
bestw=cw;
else//进入右子树
x[i]=0;
while(cw+r<
=bestw)
{//剪枝回溯
i--;
while(i>
0)
{
r+=w[i];
i--;
}
//从右子树返回
if(i==0)
returnbestw;
cw-=w[i];
}
}
5、实验结果
6、实验总结
WelcomeTo
Download!
!
欢迎您的下载,资料仅供参考!
7、
8、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 算法 装载 问题