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

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

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

2、inti=1;i<+n;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);//调用Selec

3、tSort函数for(intk=1;k<=n;k++){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数组数据拷贝到数组tempArr

4、ay中for(inte=1;e<=n;e++){t[e]=e;}for(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=

5、temp;}intmain(){floatc;//l轮船总载重intx[N+1];//装载结果（0与1分别表示是否装入inta;//集装箱数量cout<<"/////////////贪心算法求解最优装载问题////////////////////"<>c;cout<<"集装箱数量：";cin>>a;float*m=newfloat[a];cout<<"待装物品的重量分别为："<

6、的重量:";cin>>m[i];}cout<

7、

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

9、]==0

10、

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