最优装载问题实验报告

最优装载问题的贪心算法实现姓名：（学号：）一、作业及实验目的通过本实验使学生掌握贪心算法基本要素、步骤及其应用二、作业及实验原理本实验是应用贪心算法用Java编程语言对给定轮船的载重量和一批集装箱，在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。最优装载问题的贪心算法见[1]的p91-92，Java编程语言见[2]。三、作业及实验内容1.计算问题及描述:问题描述：给定轮船的载重量c，第n个集装箱及其重量w[n]，将尽可能多得集装箱装上轮船。设第i个集装箱为iw，最多可放数量n个。问题形式为:1maxniix1niiiwxcx(0,1),1xin2.算法设计及描述：验证问题是否符合贪心算法：(1)该问题具备贪心选择性质:c为定值时，iw越小时，可装载的集装箱数量n越大。问题划分为m个子问题，只要依次选择最小重量集装箱，满足小于等于c。原问题即可由n个子问题的最优解得到整体的最优解。则最优装在问题具有贪心选择性质。1122nnmmymaxxwxwxwxw先排序整个集装箱，然后尽可能多地选出前n个集装箱，要求1122nnmmymaxxwxwxwxwc.输出所选集装箱编号。(2)该问题具备最优子结构性质:一个问题的最优解包含其子问题的最优解，所以，最优装载问题具有最优子结构性质。(3)由于最优装载问题的贪心选择性质和最优子结构性质，最优装载问题符合贪心算法。3.算法分析：给出具体的算法复杂度—算法运行时间的渐近表示排序的时间复杂度为Onlogn，for循环的时间复杂度为()on；所以空间复杂度为O(m)。4.程序设计:根据所设计的算法,写出完整的算法Java程序或其他语言程序,并给出相应的程序运行结果算法的程序实现：#includestdafx.hvoidoutputResult(int*r,intlen){printf(结果：);for(inti=0;ilen;i++){printf(%d\t,r[i])}printf(\n);}voidsortBox(int*box,intn){for(inti=n-1;i0;i--){for(intj=0;ji;j++){if(box[j]box[j+1]){inttemp=boa[j];box[j]=box[j+1];box[j+1]=temp;}}}}voidloading(int*box,int*r,intw,intn){r[0]=1;w=box[0];for(inti=1;in;i++){if(w-box[i]=0){w-=box[i];r[i]=1;}}}int_tmain(intargc,_TCHAR*argv[]){intw=100;intbox[6]={100,20,25,25,20,20};sortBox(box,6);intresult[6]={0};loading(box,result,w,6);outputResult(result,6);getchar();return0;}5.实验总结：写出本次作业及实验心得通过本次实验，我们加深领会了贪心算法的中心思想，实验过程中，需要运用了最优子结构性质，贪心选择性质等等，通过对这些知识点得运用，我们更加深层次的了解贪心算法的精髓。。参考文献[1]王晓东编.算法设计与分析（第3版）.清华大学出版社.2016.[2]吴仁群编.Java基础教程.清华大学出版社.2009.