贪心算法解决最优装载问题

//author : Kevin Black

//这个是我刚刚做好的作业，我觉得应该上传一些文档到豆丁

//老师···假如你看到我的作业跟网上的这个文章一样···你别以为我是抄的啊··· //记得看看作者的名字啊！！

贪心算法之最优装载问题

一. 实验目的

掌握贪心算法的基本思想（具体阐述）

掌握贪心算法的基本要素：贪心选择性质和最优子结构性质

二. 实验内容

贪心算法基本思想：

整体划分成部分，分而治之。每个部分中寻找最优解，然后综合所有部分最优解。这是，可能得到整体的最优解，但往往得到的是近似的最优解。

贪心算法基本要素：

1. 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

2. 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

最优装载问题

1. 问题描述：

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

2. 数学描述：

三. 实验程序及运行结果

#include<iostream.h>

#include<stdlib.h>

void Swap(int &x,int &y)//交换

{

int t;

t=x;

x=y;

y=t;

}

void sort(int w[],int t[],int n)//排序，由小到大

{

for(int m=0;m<n;m++) //为每个物品编序号

{

t[m]=m;

}

int i,j;

int lastExchangeIndex;

i=n-1;

while(i>0)

{

lastExchangeIndex=0;

for(j=0;j<i;j++)

{

if(w[j+1]<w[j])

{

Swap(w[j+1],w[j]); //物品重量交换

lastExchangeIndex=j;

Swap(t[j],t[j+1]); //物品序号交换

}

}

i=lastExchangeIndex; //当不存在交换的时候，lastExchangeIndex = 0，循环结束 }

}

void Loading(int x[],int w[],int c,int n,int *t) //传址

{

sort(w,t,n);

for(int i=0;i<n;i++)x[i]=0;

for(int j=0; j<n && w[t[j]]<=c ; j++)

{

x[t[j]]=1;//装入

c-=w[t[j]];

}

}

int main()

{

int n,c;

cout<<"请输入物品个数："<<endl;

cin>>n;

cout<<"请输入最大容量："<<endl;

cin>>c;

int *t=new int[n]; //存储物品编号

int *w=new int[n]; //存储每个物品重量

for(int i=0;i<n;i++)

{

cout<<"请输入第"<<i<<"个物品重量："<<endl;

cin>>w[i];

}

int *x=new int[n]; //物品是否装入

for(int j=0;j<n;j++) //初始化 所有物品均为不装入

{

x[j]=0;

}

Loading(x,w,c,n,t);

cout<<"装入物品编号为："<<endl;

for(int k=0;k<n;k++)

{

if(x[k]==1)

cout<<t[k]+1<<" ";

}

//释放数组资源空间

delete []t;

delete []w;

delete []x;

return 0;

}

四．实验分析

证明：

1. 最优装在问题具有贪心选择性质：

分析：当载重量为定值c时，Wi越小时，可装载的集装箱数量n越大。问题划分为i个子问题，只要依次选择最小重量集装箱，满足小于等于c。原问题即可由i个子问题的最优解得到整体的最优解。所以，最优装在问题具有贪心选择性质。

y = max(x1w1 + x2w2 + … + xiwi + … + xnwn)

具体的做法：首先排序整个集装箱（依照重量从小到大的顺序），然后尽可能多地选出前i个集装箱，要求 y = (x1w1 + x2w2 + … + xiwi) <= c.

输出所选集装箱编号。

任务完成。

2. 最优装载问题具有最优子结构性质：

分析：由2中的分析可以看出，一个问题的最优解包含其子问题的最优解，所以，最优装载问题具有最优子结构性质。

3. 由于最优装载问题的贪心选择性质和最优子结构性质，最优装载问题符合贪心算法。 参考文献

[1] http:///sfzx/jpsykc/xlcad/xu04.html#(18)