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

《贪心算法解决最优装载问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中期课程设计报告//author:KevinBlack//这个是我刚刚做好的作业，我觉得应该上传一些文档到豆丁//老师···假如你看到我的作业跟网上的这个文章一样···你别以为我是抄的啊···//记得看看作者的名字啊！！贪心算法之最优装载问题一.实验目的掌握贪心算法的基本思想（具体阐述）掌握贪心算法的基本要素：贪心选择性质和最优子结构性质二.实验内容贪心算法基本思想：整体划分成部分，分而治之。每个部分中寻找最优解，然后综合所有部分最优解。这是，可能得到整体的最优解，但往往得到的是近似的最优解。贪心算法基本

2、要素：1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。最优装载问题1.问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。2.数学描述：4中期课程设计报告三.实验程序及运行结果#include<

3、iostream.h>#includevoidSwap(int&x,int&y)//交换{intt;t=x;x=y;y=t;}voidsort(intw[],intt[],intn)//排序，由小到大{for(intm=0;m0){lastExchangeIndex=0;for(j=0;j

4、+1],w[j]);//物品重量交换lastExchangeIndex=j;Swap(t[j],t[j+1]);//物品序号交换}}i=lastExchangeIndex;//当不存在交换的时候，lastExchangeIndex=0，循环结束}}voidLoading(intx[],intw[],intc,intn,int*t)//传址{sort(w,t,n);for(inti=0;i

5、]]=1;//装入c-=w[t[j]];}}intmain(){intn,c;cout<<"请输入物品个数："<>n;cout<<"请输入最大容量："<>c;int*t=newint[n];//存储物品编号int*w=newint[n];//存储每个物品重量for(inti=0;i>w[i];}int*x=newint[n];//物品是否装入for(intj=0;j

6、//初始化所有物品均为不装入{x[j]=0;}Loading(x,w,c,n,t);cout<<"装入物品编号为："<

7、，满足小于等于c。原问题即可由i个子问题的最优解得到整体的最优解。所以，最优装在问题具有贪心选择性质。y=max(x1w1+x2w2+…+xiwi+…+xnwn)具体的做法：首先排序整个集装箱（依照重量从小到大的顺序），然后尽可能多地选出前i个集装箱，要求y=(x1w1+x2w2+…+xiwi)<=c.输出所选集装箱编号。任务完成。2.最优装载问题具有最优子结构性质：分析：由2中的分析可以看出，一个问题的最优解包含其子问题的最优解，所以，最优装载问题具有最优子结构性质。3.由于最优装载问题的贪心选择性质和

8、最优子结构性质，最优装载问题符合贪心算法。参考文献[1]http://www.xinx.sdnu.edu.cn/sfzx/jpsykc/xlcad/xu04.html#(18)4