裝載問題

實驗七：回溯法裝載問題

一、實驗目的與要求

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

并行計算解決部隊鐵路梯隊裝載NP問題應用研究04-27

心身問題的問題式04-29

裝載機管理制度05-31

用問題來扼殺問題04-30

大學問題與問題大學05-02

從歸納問題到演繹問題04-28

問題04-30

問題05-01

重型裝備鐵路裝載橫向移位裝置研究04-27