《算法设计与分析贪心算法最优装载.docx》由会员分享，可在线阅读，更多相关《算法设计与分析贪心算法最优装载.docx（5页珍藏版）》请在三一办公上搜索。
1、算法设计与分析贪心算法最优装载计算机算法与设计 实验内容：贪心算法-最优装载 问题描述：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 问题分析： 该问题可形式化描述为： maxxii=1nnxi0,1,1in wxc iii=1算法描述：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下： Template Void Loading(int x,Type w,Type c ,int n) int *t = new int n+1; Sort(w
2、,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
3、= 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(in
4、t 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; cout待装物品的重量分别为：endl; for(int i = 1;i=a;i+)
5、 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个集装箱不装入 endl; else cout第b个集装箱装入 endl; cout/结/endl; system(pause); return 0; 束
