背包問題的貪心算法.doc

《背包問題的貪心算法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、貪心方法：總是對(duì)當(dāng)前的問題作最好的選擇，也就是局部尋優(yōu)。最后得到整體最優(yōu)。應(yīng)用：1：該問題可以通過“局部尋優(yōu)”逐步過渡到“整體最優(yōu)”。貪心選擇性質(zhì)與“動(dòng)態(tài)規(guī)劃”的主要差別。2：最優(yōu)子結(jié)構(gòu)性質(zhì)：某個(gè)問題的整體最優(yōu)解包含了“子”問題的最優(yōu)解。代碼如下：#includestructgoodinfo{?floatp;?//物品效益?floatw;?//物品重量?floatX;?//物品該放的數(shù)量?intflag;?//物品編號(hào)};//物品信息結(jié)構(gòu)體voidInsertionsort(goodinfogoods[],intn){?intj,i;?for(j

2、=2;j<=n;j++)?{??goods[0]=goods[j];????i=j-1;????while(goods[0].p>goods[i].p)??{???goods[i+1]=goods[i];???i--;??}??goods[i+1]=goods[0];?}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){???floatcu;?inti,j;?for(i=1;i<=n;i++)??goods[i].X=0;?cu=M;?//背包剩余容量?for(i=1;i

3、i].w>cu)//當(dāng)該物品重量大與剩余容量跳出???break;?????goods[i].X=1;???cu=cu-goods[i].w;//確定背包新的剩余容量?}?if(i<=n)??goods[i].X=cu/goods[i].w;//該物品所要放的量/*按物品編號(hào)做降序排列*/??for(j=2;j<=n;j++)?{??goods[0]=goods[j];????i=j-1;????while(goods[0].flag

4、[0];?}///////////////////////////////////////////?cout<<"最優(yōu)解為:"<

5、--------運(yùn)用貪心法解背包問題---------

6、"<

7、---powerbyzhanjiantao(028054115)---

8、"<

9、--------------------------

10、-----------

11、"<>n;?goods=newstructgoodinfo[n+1];//?cout<<"請(qǐng)輸入背包的最大容量：";?cin>>M;?cout<>goods[i].w;???cout<<"請(qǐng)輸入第"<

12、<"件物品的效益:";???cin>>goods[i].p;???goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比???cout<torunagian"<toexit"<>j;?}}#include#include#defineMax100/*定義棧結(jié)構(gòu)*/typedefstructlis

13、t{?intdata[Max];?inttop;}Seqstack;/*定義一個(gè)用來存儲(chǔ)結(jié)果的鏈表*/typedefstructList{?Seqstackresult;?structList*Next;}Seqlist,*Pointer;voidInicial_List(Pointerp){?p=(Pointer)malloc(sizeof(Seqlist));?p->Next=NULL;}SeqstackPush_Stack(intn,Seqstacks){?s.top++;?s.data[s.top]=n;?returns;}int