最新背包问题的贪心算法.doc

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

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

2、的数量  intflag; //物品编号 };//物品信息结构体 voidInsertionsort(goodinfogoods[],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];  }}//按物品效益，重量比值做升序排列 voi

3、dbag(goodinfogoods[],floatM,intn) {     float收集于网络，如有侵权请联系管理员删除__________________________________________________cu;  inti,j;  for(i=1;i<=n;i++)   goods[i].X=0;  cu=M; //背包剩余容量  for(i=1;icu)//当该物品重量大与剩余容量跳出    break;       goods[i]

4、.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

5、];  } ///////////////////////////////////////////  cout<<"最优解为:"<

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

7、"<

8、---powerby收集于网络，如有侵权请联系管理员删除___________

9、_______________________________________zhanjiantao(028054115)---

10、"<

11、-------------------------------------

12、"<>n;  goods=newstructgoodinfo[n+1];//  cou

13、t<<"请输入背包的最大容量：";  cin>>M;  cout<>goods[i].w;    cout<<"请输入第"<>goods[i].p;    goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比    cout<

14、  }   Insertionsort(goods,n);  bag(goods,M,n);  cout<<"press<1>torunagian"<toexit"<>j;  } }收集于网络，如有侵权请联系管理员删除__________________________________________________