- 相關推薦
裝載問題
實驗七:回溯法裝載問題
一、實驗目的與要求
1、掌握裝載問題的算法;
2、初步掌握回溯算法
二、實驗題:
問題描述:
有兩艘船,它們的可裝載的貨物重量分別為c1,c2,給定一批貨物,其重量保存在數(shù)組w[i]中了,問這批貨物能否用此兩艘船送出。\
#include
using namespace std;
class Loading
{friend float MaxLoading
(float[],float,int);
public:
void Backtrack(int i);
int n;
int *x,*bestx;
float *w,c,cw,bestw,r;
};
float Maxloading(float w1[],float c1,
float c2,int n1,int bestx1[])
{ Loading k;
int j;
float MAXLoad;
k.x= new int [n1+1];
k.bestx=bestx1;
k.w = w1;
k.c = c1;
k.n = n1;
k.cw = 0;
k.bestw = 0;
k.r = 0;
for(int i=1;i<=n1;i++)
k.r+=w1[i];
k.Backtrack(1);
delete [] k.x;
cout<<"船1最優(yōu)裝載:"<<k.bestw<<endl;
MAXLoad=k.bestw;
for( j=1;j<=n1;j++)
{if(k.bestx[j]==0)
{ MAXLoad+=w1[j];
c2-=w1[j];
if(c2<0)
{cout<<"找不到合理裝載方案!"<<endl;
return -1;
}
}
}
cout<<"船1中的箱子:";
for( j=1;j<=n1;j++)
if(k.bestx[j]==1)
cout<<j<<" ";
cout<<endl;
cout<<"船2中的箱子:";
for( j=1;j<=n1;j++)
if(k.bestx[j]==0)
cout<<j<<" ";
cout<<endl;
return MAXLoad;
}
void Loading::Backtrack(int i)
{ if(i>n)
{if(cw>bestw)
{for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestw = cw;
}
return;
}
r裝載問題-=w[i];
if(cw+w[i]<=c)
{x[i]=1;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw)
{x[i] = 0;
Backtrack(i+1);}
r+=w[i];
}
int main()
{float w[20];
float c1,c2,k;
int n,bestx[20];
cout<<"輸入箱子數(shù):";
cin>>n;
cout<<"輸入箱子重量:";
for(int i=1;i<=n;i++)
cin>>w[i];
cout<<"輸入容量船1,船2:";
cin>>c1>>c2;
k=Maxloading(w,c1,c2,n,bestx);
if(k!=-1)cout<<"總體最優(yōu)裝載:"<<k<<endl; return 1;
}
【裝載問題】相關文章:
鐵路貨物裝載加固中存在的問題及對策淺析04-28
心身問題的問題式04-29
裝載機管理制度05-31
用問題來扼殺問題04-30
大學問題與問題大學05-02
從歸納問題到演繹問題04-28
問題04-30
問題05-01
重型裝備鐵路裝載橫向移位裝置研究04-27