欢迎来到天天文库
浏览记录
ID:9949082
大小:85.00 KB
页数:9页
时间:2018-05-16
《算法设计与分析-贪心算法-最优装载》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、计算机算法与设计实验内容:贪心算法-最优装载问题描述:有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi,最优装载问题要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。问题分析:该问题可形式化描述为:算法描述:最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。具体算法描述如下:TemplateVoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<+n;i++){x[i]=
2、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++){x[k]=0;//初始化数组x[
3、]}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(inti=1;i4、从小到大排列{min=i;for(intj=i+1;j<=n;j++){if(tempArray[min]>tempArray[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];//装载结果(0与1分别表示是否装入inta;//集装箱数量cout<<"//////////5、///贪心算法求解最优装载问题////////////////////"<>c;cout<<"集装箱数量:";cin>>a;float*m=newfloat[a];cout<<"待装物品的重量分别为:"<>m[i];}cout<6、,c,a);cout<<"对应的贪心选择结果为:"<7、8、x[f]==1)cout<9、10、x[b]==1){if(x[b]==0){cout<<"第"<11、///////////////////////"<
4、从小到大排列{min=i;for(intj=i+1;j<=n;j++){if(tempArray[min]>tempArray[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];//装载结果(0与1分别表示是否装入inta;//集装箱数量cout<<"//////////
5、///贪心算法求解最优装载问题////////////////////"<>c;cout<<"集装箱数量:";cin>>a;float*m=newfloat[a];cout<<"待装物品的重量分别为:"<>m[i];}cout<6、,c,a);cout<<"对应的贪心选择结果为:"<7、8、x[f]==1)cout<9、10、x[b]==1){if(x[b]==0){cout<<"第"<11、///////////////////////"<
6、,c,a);cout<<"对应的贪心选择结果为:"<7、8、x[f]==1)cout<9、10、x[b]==1){if(x[b]==0){cout<<"第"<11、///////////////////////"<
7、
8、x[f]==1)cout<9、10、x[b]==1){if(x[b]==0){cout<<"第"<11、///////////////////////"<
9、
10、x[b]==1){if(x[b]==0){cout<<"第"<
11、///////////////////////"<
此文档下载收益归作者所有