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

1、计算机算法与设计实验内谷：贪心算法-最优装载问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi,最优装载问题要求在装载体积不受限制的情况 下，将尽可能多的集装箱装上轮船。问题分析：该问题可形式化描述为：nmax、xii 4n' WjXj _c x 101訂 _i _ ni吕算法描述：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述 如下：Templatevclass Type>Void Loadi ng(i nt x,Type w,Type c ,int n)int *t = new int n+1;

2、Sort(w,t ,n);for(i nt i =1;i<+n;i+)xi = 0;for (int i = 1;i<=n&&wtiv=c;i+)xti = 1;c-= wti;所需计算时间为0(nlogn)运行结果：'c:u5er5lj-zh a odocumentsvi s u a I studio 2010戸心£<5贪心算法%命小贪心算法£)«'='- EI> -39- r-lr -3? -33-另选一组数据输入:卸23/ 1 ,"":重为貝I I "重数口囂第第第

3、第第 兀入入入入入 "篁幫请谓请请请3 5 6 9 5 42 4 2 5 7 1 BBB一 量帘Gy量量 二B-.E'dlul _&_ 二 R1-=nl-_ 勺亘冒宜建亘建*£O -EllulkuluE隹ML長灵 .atttttt 12 3 4 5 645taabx不不装EEfhlju 巨匚g-L'-_bilU lull . 务 12 3 4 5 6 義MT第幕幕幕入人'结审'优装鼓可题""""""""""750141详细设计：#in

4、elude <iostream>using n amespace std;con st int N = 100;templatevclass Type>void Load in g(i ntx,Type w, Type c, int n)int *t = new int n+1;/Sort(w, t, n); / 调用 SelectSort函数for(i nt k=1; k<二n; k+)xk = 0;/初始化数组xfor(i nt i=1; i<=n && wtiv=c; i+)xti = 1;/经判断该集装箱可以装入c -= wti;/轮船可栽

5、重相应减少 templatevclass Type>void Sort(Type w,i nt *t,i nt n)Type tempArrayN+1,temp;int min;memcpy(tempArray,w,(n+1)*sizeof(Type);/将 w 数组数据拷贝到 数组tempArray中for(i nt e=1;e< 二n; e+)te = e;for(int i=1;i<n;i+) /类冒泡算法，将集装箱按重量从小到大排列min 二i;for(i nt j二i+1;jv 二n ;j+)if(tempArraymi n>tempArrayj)min二j;

6、Swap(tempArrayi,tempArraymi n);Swap(ti,tmi n);template vclass Type>void Swap(Type &x,Type &y) /swap 函数Type temp = x;x = y;y = temp;int mai n()float c ; l轮船总载重int xN+1;/装载结果(0与1分别表示是否装入int a ;/集装箱数量cout <<"/ 贪心算法求解最优装载问题 /"vvendl;coutvv"轮船载重为："cin> >c;coutvv

7、"集装箱数量："cin> >a;float *m = new float a;coutvv"待装物品的重量分别为："<<e ndl;for(i nt i = 1;i<=a;i+)coutvv"请输入第"vvivv"个集装箱的重量：" ci n>> mi;cout«e ndl;coutvv"集装箱列表："<<e ndl;for(i nt j=1; j<二a; j+)cout<<mjvv"t"coutvve ndl;Loadi ng(x,m,c,a);coutvv"对应的贪心选择结果为:"<<endl;for(i nt f=1; f<=a; f+)if(xf=0|xf=1)cout<<xfvv"t"coutvve ndl;coutvv"集装箱最优装载情况:"vvendl;for(i nt b=1; b