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

计算机算法与设计实验内容：贪心算法-最优装载问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题分析： 该问题可形式化描述为： 算法描述：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下：TemplateVoid Loading(int x,Type w,Type c ,int n)int *t = new int n+1;Sort(w,t,n);for(int i =1;i+n;i+) xi = 0; for (int i = 1;i=n&wti=c;i+) xti = 1; c-= wti;所需计算时间为O(nlogn)运行结果：另选一组数据输入：详细设计：#include using namespace std; const int N = 100; template void Loading(int x,Type w, Type c, int n) int *t = new int n+1;/ Sort(w, t, n); /调用SelectSort函数 for(int k=1; k=n; k+) xk = 0;/初始化数组x for(int i=1; i=n & wti=c; i+) xti = 1; /经判断该集装箱可以装入 c -= wti; /轮船可栽重相应减少 template void Sort(Type w,int *t,int n) Type tempArrayN+1,temp; int min; memcpy(tempArray,w,(n+1)*sizeof(Type);/将w数组数据拷贝到数组tempArray中 for(int e=1;e=n;e+) te = e; for(int i=1;in;i+) /类冒泡算法，将集装箱按重量从小到大排列 min=i; for(int j=i+1;jtempArrayj) min=j; Swap(tempArrayi,tempArraymin); Swap(ti,tmin); template void Swap(Type &x,Type &y) /swap函数 Type temp = x; x = y; y = temp; int main() float c ; /l轮船总载重 int xN+1; /装载结果（0与1分别表示是否装入int a ;/集装箱数量 cout /贪心算法求解最优装载问题/endl; coutc; couta;float *m = new float a; cout待装物品的重量分别为：endl; for(int i = 1;i=a;i+) cout请输入第imi; coutendl; cout集装箱列表：endl;for(int j=1; j=a; j+) coutmjt; coutendl; Loading(x,m,c,a); cout对应的贪心选择结果为:endl; for(int f=1; f=a; f+) if(xf=0|xf=1) coutxft; coutendl; cout集装箱最优装载情况:endl; for(int b=1; b=a; b+) if (xb=0|xb=1)if (xb=0) cout 第b个集装