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

计算机算法与设计实验内容：贪心算法-最优装载问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题分析：该问题可形式化描述为：niix1maxcxwniii1nixi1,1,0算法描述：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下：TemplateclassTypeVoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(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)运行结果：另选一组数据输入：详细设计：#includeiostreamusingnamespacestd;constintN=100;templateclassTypevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];//Sort(w,t,n);//调用SelectSort函数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]];//轮船可栽重相应减少}}templateclassTypevoidSort(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;in;i++)//类冒泡算法，将集装箱按重量从小到大排列{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]);}}templateclassTypevoidSwap(Type&x,Type&y)//swap函数{Typetemp=x;x=y;y=temp;}intmain(){floatc;//l轮船总载重intx[N+1];//装载结果（0与1分别表示是否装入inta;//集装箱数量cout/////////////贪心算法求解最优装载问题////////////////////endl;cout轮船载重为：;cinc;cout集装箱数量：;cina;float*m=newfloat[a];cout待装物品的重量分别为：endl;for(inti=1;i=a;i++){cout请输入第i个集装箱的重量:;cinm[i];}coutendl;cout集装箱列表：endl;for(intj=1;j=a;j++){coutm[j]\t;}coutendl;Loading(x,m,c,a);cout对应的贪心选择结果为:endl;for(intf=1;f=a;f++){if(x[f]==0||x[f]==1)coutx[f]\t;}coutendl;cout集装箱最优装载情况:endl;for(intb=1;b=a;b++){if(x[b]==0||x[b]==1){if(x[b]==0){cout第b个集装箱不装入endl;}else{cout第b个集装箱装入endl;}}}cout///////////////////////结束////////////////////////////endl;system(pause);return0;}