算法分析與設(shè)計-貪心算法

《算法分析與設(shè)計-貪心算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、專業(yè)課程實驗報告課程名稱:算法分析與設(shè)計開課學(xué)期：2014至2015學(xué)年第1學(xué)期專業(yè)：軟件工程年級班級：2012級03班學(xué)生姓名：李明洋學(xué)號：222012321062053曹嚴(yán)元實驗教師:計算機與信息科學(xué)學(xué)院軟件學(xué)院實驗項目名稱貪心算法實驗時間2014年門月14實驗類型□驗證性□設(shè)計性□綜合性日「一、實驗?zāi)康?.掌握貪心法的基本思想方法；2.了解適用于用貪心法求解的問題類型，并能設(shè)計相應(yīng)貪心法算法；3.學(xué)握貪心算法復(fù)雜性分析方法分析問題復(fù)雜性。二、實驗要求1.預(yù)習(xí)實驗指導(dǎo)書及教材的有關(guān)內(nèi)容，掌握貪心算法的基本思想；2.嚴(yán)格按照實驗內(nèi)容進行實驗，培養(yǎng)良好的算法

2、設(shè)計和編程的習(xí)慣；3.認(rèn)真聽講，服從安排，獨立思考并完成實驗。三、實驗內(nèi)容與設(shè)計(主要內(nèi)容，操作步驟、算法描述或程序代碼)實現(xiàn)背包問題的貪心算法procedureKNAPSACK(P,W,M,X,n)//P(l：n)和W(l；n)分別含有按P(i)/W(i)>P(i+l)/W(i+l)排序的n件物品的效益值和重SoM是背包的容量大小，而x(l：n)是解向量realP(l：n),W(l：n),X(l：n),M,cu；integeri,n；X-0//將解向量初始化為零cu—M//cu是背包剩余容量fori—1tondoifW(i)>cuthenexitendif

3、X(i)Tcu*-cu-W(i)repeatifiWnthenX(i)—cu/W(i)endifendGREEDY-KNAPSACKprocedureprini(G,)status*-"unseen”//T為空status[1]“treenode”//將1放入Tforeachodge(l,w)dostatus[w]*-"fringe”//找到T的鄰接點dad[w]—1;//w通過1與T建立聯(lián)系dist[w]—weight(1,w)//w到T的距離repeatwhilestatus[t]H“treenode"dopickafringeuwithmindistW

4、//選取到T最近的節(jié)點status[u]—“treenode”foreachedge(u,w)do修改w和T的關(guān)系repeatrepeat程序代碼：#includeh>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品該放的數(shù)量intflag;//物品編號}；//物品信息結(jié)構(gòu)體voidInsertionsort@oodinfogoods[],intn){intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];while(goods[0].p>goods[i

5、].p){goods[i+l]=goods[i];i—；}goods[i+l]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=l;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=l;icu)//當(dāng)該物品重量大與剩余容量跳出break;goods[i].X二1;cu二cu-goods[i].v;//確定背包新的剩余容量}if(i<=n)goods[i]?X=

6、cu/goods[i]?w;//該物品所要放的量for(j=2;j<=n;j++)goods[0]=goods[j];i=j-l；while(goods[0].flag

7、運用貪心法解背包問題

8、/z?endl;cout<<"

9、1，z?en

10、dl:intj;intn;floatM;goodinfo*goods;//定義一個指針while(j){cout?，z請輸入物品的總數(shù)量：〃；cin?n;goods二newstructgoodinfo[n+1];//cout?，z請輸入背包的最大容量：〃；cin?M;cout<

11、goods[i]?w;〃得出物品的效益,重量比cou