背包问题的贪心算法.doc

《背包问题的贪心算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。代码如下：#includestructgoodinfo{ floatp; //物品效益 floatw; //物品重量 floatX; //物品该放的数量 intflag; //物品编号};//物品信息结构体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)//当该物品重量大与剩余容量跳出   break;     goods[i].X=1;   cu=cu-goods[i].w;//确定背包新的剩余容量 } if(i<=n)  goods[i].X=cu/goods[i].w;//该物品所要放的量/*按物品编号做降序排列*/  for(j=2;j<=n;j++) {  goods[0]=goods[j];    i=j-1;    while(goods[0].flag

4、[0]; }/////////////////////////////////////////// cout<<"最优解为:"<

5、--------运用贪心法解背包问题---------

6、"<

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

8、"<

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

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

11、"<>n; goods=newstructgoodinfo[n+1];// cout<<"请输入背包的最大容量："; cin>>M; cout<>goods[i].w;   cout<<"请输入第"<

12、<"件物品的效益:";   cin>>goods[i].p;   goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比   cout<torunagian"<toexit"<>j; }}#include#include#defineMax100/*定义栈结构*/typedefstructlis

13、t{ intdata[Max]; inttop;}Seqstack;/*定义一个用来存储结果的链表*/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