算法設(shè)計與分析-貪心算法-最優(yōu)裝載

1、計算機算法與設(shè)計實驗內(nèi)谷：貪心算法-最優(yōu)裝載問題描述：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi,最優(yōu)裝載問題要求在裝載體積不受限制的情況 下，將盡可能多的集裝箱裝上輪船。問題分析：該問題可形式化描述為：nmax、xii 4n' WjXj _c x 101訂 _i _ ni呂算法描述：最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述 如下：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)運行結(jié)果：'c:u5er5lj-zh a odocumentsvi s u a I studio 2010戸心£<5貪心算法%命小貪心算法£)«'='- EI> -39- r-lr -3? -33-另選一組數(shù)據(jù)輸入:卸23/ 1 ,"":重為貝I I "重數(shù)口囂第第第

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 . 務(wù) 12 3 4 5 6 義MT第幕幕幕入人'結(jié)審'優(yōu)裝鼓可題""""""""""750141詳細設(shè)計：#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); / 調(diào)用 SelectSort函數(shù)for(i nt k=1; k<二n; k+)xk = 0;/初始化數(shù)組xfor(i nt i=1; i<=n && wtiv=c; i+)xti = 1;/經(jīng)判斷該集裝箱可以裝入c -= wti;/輪船可栽

5、重相應(yīng)減少 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 數(shù)組數(shù)據(jù)拷貝到 數(shù)組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 函數(shù)Type temp = x;x = y;y = temp;int mai n()float c ; l輪船總載重int xN+1;/裝載結(jié)果(0與1分別表示是否裝入int a ;/集裝箱數(shù)量cout <<"/ 貪心算法求解最優(yōu)裝載問題 /"vvendl;coutvv"輪船載重為："cin> >c;coutvv

7、"集裝箱數(shù)量："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"對應(yīng)的貪心選擇結(jié)果為:"<<endl;for(i nt f=1; f<=a; f+)if(xf=0|xf=1)cout<<xfvv"t"coutvve ndl;coutvv"集裝箱最優(yōu)裝載情況:"vvendl;for(i nt b=1; b