文档库

最新最全的文档下载
当前位置:文档库 > 实验五 箱子装载问题(分支限界法)

实验五 箱子装载问题(分支限界法)

实验五箱子装载问题

一、实验目的:

1、理解和复习所学各种算法的概念;

2、掌握和复习所学各种算法的基本要素;

3、掌握各种算法的优点和区别;

4、通过应用范例掌握选择最佳算法的设计技巧与策略;

二、实验内容及要求:

1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。(任选两种)

2、通过上机实验进行算法实现。

3、保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。

三、实验原理:

回溯法原理:

从开始结点出发,以深度优先方式搜索整个解空间。这个节点成为活结点,同时也成为当前的扩展节点。在当前的扩展节点处,搜索向纵深方向一致一个新节点。

贪心算法原理:

贪心算法通过一系列的选择来得到问题的解。他所做的每一个选择都是当前状态下局部最好选择,即贪心选择。

四、程序代码:

贪心算法:

#include

#include

#define N 100

using namespace std;

int main(){

int t[N],w0[N],w[N],n,c,m,i,j;

int max=0,weight=0;

bool tx[N];

cout<<"请输入轮船的载重量c:"<

cin>>c;

cout<<"请输入可以装入的集装箱的数目n:"<

cin>>n;

cout<<"请输入各集装箱的重量w[i](1<=i<=n):"<

cin>>w0[i];

w[i+1]=w0[i];

tx[i+1]=false;

}

for(i=1;i

for(j=i+1;j<=n;j++){

if(w[i]>w[j]) {

int tem;

tem=w[j];

w[j]=w[i];

w[i]=tem;

}

}

}

for(i=1;i<=n;i++)printf("%d ",w[i]);

printf("n");

for(i=1;i<=n;i++){

int min=weight+w[i];

if(min<=c){

weight+=w[i];

tx[i]=true;

}

}

m=i-1;

cout<<"最优装载情况为:"<

cout<<"装入轮船的集装箱为:";

max=0;

for(i=1;i<=m;i++){

if(tx[i]){max+=w[i];cout<

}

cout<

cout<<"装入的集装箱的最大重量为:"<

system("pause");

}

回溯法:

#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最优装载:"<

MAXLoad=k.bestw;

for( j=1;j<=n1;j++)

{

if(k.bestx[j]==0)

{

MAXLoad+=w1[j];

c2-=w1[j];

if(c2<0)

{

cout<<"找不到合理装载方案!"<

return -1;

}

}

}

cout<<"船1中的箱子:";

for( j=1;j<=n1;j++)

if(k.bestx[j]==1)

cout<

cout<

cout<<"船2中的箱子:";

for( j=1;j<=n1;j++)

if(k.bestx[j]==0)

cout<

cout<

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<<"输入箱子数:";

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<<"总体最优装载:"<

return 1;

}

五、结果运行与分析:

贪心算法:

实验五  箱子装载问题(分支限界法)

回溯法:

实验五  箱子装载问题(分支限界法)

六、心得与体会:

通过本次实验,自己再次的联系了贪心算法和回溯法的应用,本次实验自己测试了很多次才成功,收获蛮大的,自己的编程能力进一步的提高了。