最优装载问题的贪心算法实现
            姓名:
                            (学号:)
一、作业及实验目的
通过本实验使学生掌握贪心算法基本要素、步骤及其应用
二、作业及实验原理
本实验是应用贪心算法用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小时内删除。