背包问题地贪心算法

《背包问题地贪心算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。代码如下：#includestructgoodinfo{ floatp; //物品效益 floatw; //物品重量 floatX; //物品该放的数量 intflag; //物品编号};//物品信息结构体voidInsertionsort(goodinfogoods[],

2、intn){ intj,i; for(j=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; 

3、cu=M; //背包剩余容量 for(i=1;icu)//当该物品重量大与剩余容量跳出   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、.flag)  {   goods[i+1]=goods[i];   i--;  }  goods[i+1]=goods[0]; }/////////////////////////////////////////// cout<<"最优解为:"<

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

6、"<

7、---

8、powerbyzhanjiantao(028054115)---

9、"<

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

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

12、=1;i<=n;i++)  { goods[i].flag=i;   cout<<"请输入第"<>goods[i].w;   cout<<"请输入第"<>goods[i].p;   goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比   cout<torunagian"<

13、l; cout<<"press<0>toexit"<>j; }}文案大全实用文档#include#include#defineMax100/*定义栈结构*/typedefstructlist{ intdata[Max]; inttop;}Seqstack;/*定义一个用来存储结果的链表*/typedefstructList{ Seqstackresult; structList*Next;}Seqlist,*Pointer;voidInicial_List(Pointerp){ 

14、p=(Pointer)malloc(sizeof(Seqlist)); p->Next=NULL;}SeqstackPush_Stack(intn,Seqstacks){ s.top++; s