最优装载问题实验报告

最优装载问题的贪心算法实现

姓名：

（学号：）

一、作业及实验目的

通过本实验使学生掌握贪心算法基本要素、步骤及其应用

二、作业及实验原理

本实验是应用贪心算法用Java编程语言对给定轮船的载重量和一批集装箱，在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。最优装载问题的贪心算法见[1] 的p91-92，Java编程语言见[2]。

三、 作业及实验内容

1. 计算问题及描述:

问题描述：给定轮船的载重量c，第n个集装箱及其重量w[n]，将尽可能多得集装箱装上轮船。

设第i个集装箱为wi，最多可放数量n个。 问题形式为:max?xi?1ni

?wx?c

iii?1xnx?(0,1),1?i?n

2. 算法设计及描述：

验证问题是否符合贪心算法：

(1)该问题具备贪心选择性质:c为定值时，wi越小时，可装载的集装箱数量n越大。问题划分为m个子问题，只要依次选择最小重量集装箱，满足小于等于c。原问题即可由n个子问题的最优解得到整体的最优解。则最优装在问题具有贪心选择性质。

y?max?x1w1?x2w2???xnwn???xmwm?

先

排序整个集装箱，然后尽可能多地选出前n个集装箱，要求

y?max?x1w1?x2w2???xnwn???xmwm??c. 输出所选集装箱编号。

(2) 该问题具备最优子结构性质:一个问题的最优解包含其子问题的最优解，所以，最优装载问题具有最优子结构性质。

(3) 由于最优装载问题的贪心选择性质和最优子结构性质，最优装载问题符合贪心算法。

3. 算法分析：给出具体的算法复杂度—算法运行时间的渐近表示 排序的时间复杂度为O复杂度为O(m)。

4. 程序设计:根据所设计的算法,写出完整的算法Java程序或 其他语言程序,并给出相应的程序运行结果 算法的程序实现： #include\

void outputResult(int *r,int len){ printf(\结果：\

for(int i=0;i

printf(\ }

printf(\ }

void sortBox(int *box,int n){ for(int i=n-1;i>0;i--) {

for(int j=0;jbox[j+1]){ int temp=boa[j]; box[j]=box[j+1]; box[j+1]=temp; } } } }

?nlogn?， for循环的时间复杂度为o(n)；所以空间

void loading(int *box,int *r,int w,int n){ r[0]=1; w=box[0];

for(int i=1;i=0){ w-=box[i]; r[i]=1; } } }

int_tmain(int argc,_TCHAR*argv[]) {

int w=100;

int box[6]={100,20,25,25,20,20}; sortBox(box,6); int result[6]={0};

loading(box,result,w,6); outputResult(result,6); getchar(); return 0; }

5. 实验总结：写出本次作业及实验心得

通过本次实验，我们加深领会了贪心算法的中心思想，实验过程中，需要运用了最优子结构性质，贪心选择性质等等，通过对这些知识点得运用，我们更加深层次的了解贪心算法的精髓。。

参考文献

[1] 王晓东编. 算法设计与分析（第3版）. 清华大学出版社. 2016. [2] 吴仁群编. Java基础教程. 清华大学出版社. 2009.