背包问题地贪心算法

背包问题地贪心算法

ID:47072021

大小:40.50 KB

页数:10页

时间:2019-07-16

背包问题地贪心算法_第1页
背包问题地贪心算法_第2页
背包问题地贪心算法_第3页
背包问题地贪心算法_第4页
背包问题地贪心算法_第5页
资源描述:

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。