最优装载问题的贪心算法实现
姓名:
(学号:)
一、作业及实验目的
通过本实验使学生掌握贪心算法基本要素、步骤及其应用
二、作业及实验原理
本实验是应用贪心算法用Java编程语言对给定轮船的载重量和一批集装箱,在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。最优装载问题的贪心算法见[1] 的p91-92,Java编程语言见[2]。
三、 作业及实验内容
1.计算问题及描述:
java安装完整教程
问题描述:给定轮船的载重量c,第n个集装箱及其重量w[n],将尽可能多得集装箱装上轮船。
设第i个集装箱为,最多可放数量n个。
问题形式为:
2.算法设计及描述:
验证问题是否符合贪心算法:
(1)该问题具备贪心选择性质:c为定值时,越小时,可装载的集装箱数量n越大。问题划分为m个子问题,只要依次选择最小重量集装箱,满足小于等于c。原问题即可由n个子问题的最优解得到整体的最优解。则最优装在问题具有贪心选择性质。
先排序整个集装箱,然后尽可能多地选出前n个集装箱,要求 输出所选集装箱编号。
(2) 该问题具备最优子结构性质:一个问题的最优解包含其子问题的最优解,所以,最优装载问题具有最优子结构性质。
(3) 由于最优装载问题的贪心选择性质和最优子结构性质,最优装载问题符合贪心算法。
3.算法分析:给出具体的算法复杂度—算法运行时间的渐近表示
排序的时间复杂度为, for循环的时间复杂度为;所以空间复杂度为O(m)。
4.程序设计:根据所设计的算法,写出完整的算法Java程序或 其他语言程序,并给出相应的程序运行结果
算法的程序实现:
#include"stdafx.h"
void outputResult(int *r,int len){
printf("结果:");
for(int i=0;i<len;i++)
{
printf("%d\t",r[i])
}
printf("\n");
}
void sortBox(int *box,int n){
for(int i=n-1;i>0;i--)
{
for(int j=0;j<i;j++){
if(box[j]>box[j+1]){
int temp=boa[j];
box[j]=box[j+1];
box[j+1]=temp;
}
}
}
}
void loading(int *box,int *r,int w,int n){
r[0]=1;
w=box[0];
for(int i=1;i<n;i++){
if(w-box[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.
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论