算法设计与分析-贪心算法-最优装载

算法设计与分析-贪心算法-最优装载

ID:33575006

大小:85.00 KB

页数:9页

时间:2019-02-27

算法设计与分析-贪心算法-最优装载_第1页
算法设计与分析-贪心算法-最优装载_第2页
算法设计与分析-贪心算法-最优装载_第3页
算法设计与分析-贪心算法-最优装载_第4页
算法设计与分析-贪心算法-最优装载_第5页
资源描述:

《算法设计与分析-贪心算法-最优装载》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、计算机算法与设计实验内容:贪心算法-最优装载问题描述:有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi,最优装载问题要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。问题分析:该问题可形式化描述为:算法描述:最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。具体算法描述如下:TemplateVoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<+n;

2、i++){x[i]=0;}for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}所需计算时间为O(nlogn)运行结果:另选一组数据输入:详细设计:#includeusingnamespacestd;constintN=100;templatevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];//Sort(w,t,n);//调用SelectSort函数for(intk=1;k<=n;k

3、++){x[k]=0;//初始化数组x[]}for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;//经判断该集装箱可以装入c-=w[t[i]];//轮船可栽重相应减少}}templatevoidSort(Typew[],int*t,intn){TypetempArray[N+1],temp;intmin;memcpy(tempArray,w,(n+1)*sizeof(Type));//将w数组数据拷贝到数组tempArray中for(inte=1;e<=n;e++){t[e]=e;}for(

4、inti=1;itempArray[j]){min=j;}}Swap(tempArray[i],tempArray[min]);Swap(t[i],t[min]);}}templatevoidSwap(Type&x,Type&y)//swap函数{Typetemp=x;x=y;y=temp;}intmain(){floatc;//l轮船总载重intx[N+1];//装载结果(

5、0与1分别表示是否装入inta;//集装箱数量cout<<"/////////////贪心算法求解最优装载问题////////////////////"<>c;cout<<"集装箱数量:";cin>>a;float*m=newfloat[a];cout<<"待装物品的重量分别为:"<>m[i];}cout<

6、j<=a;j++){cout<

7、

8、x[f]==1)cout<

9、

10、x[b]==1){if(x[b]==0){cout<<"第"<

11、<

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。