详解贪心法求解背包问题

来源:爱站网时间:2021-02-11编辑:网友分享
算法可以为我们解决很多问题,但是这在很多实现中是最佳的选择,让爱站技术频道小编带你一起进入下文学习详解贪心法求解背包问题,希望能为你带来帮助。

算法可以为我们解决很多问题,但是这在很多实现中是最佳的选择,让爱站技术频道小编带你一起进入下文学习详解贪心法求解背包问题,希望能为你带来帮助。

贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。
应用:
1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。
2:最优子结构性质:某个问题的整体最优解包含了“子”问题的最优解。
完整的代码如下:

 

 

 

 


#include "iostream"
using namespace std;
struct goodinfo
{
 float p; //物品效益
 float w; //物品重量
 float X; //物品该放的数量
 int flag; //物品编号
};//物品信息结构体
void Insertionsort(goodinfo goods[],int n)
{
 int j,i;
 for(j=2;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];
 }
}//按物品效益,重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
 float cu;
 int i,j;
 for(i=1;i   goods[i].X=0;
 cu=M;  //背包剩余容量
 for(i=1;i  {
  if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
   break;
  goods[i].X=1;
  cu=cu-goods[i].w;//确定背包新的剩余容量
 }
 if(i   goods[i].X=cu/goods[i].w;//该物品所要放的量
 //按物品编号做降序排列
 for(j=2;j  {
  goods[0]=goods[j];
  i=j-1;
  while (goods[0].flag   {
   goods[i+1]=goods[i];
   i--;
  }
  goods[i+1]=goods[0];
 }
 cout  for(i=1;i  {
  cout   cout  }
}
int main(void)
{
 cout  cout  int i,j,n;
 float M;
 goodinfo *goods;     //定义一个指针
 cout to run the program"  cout to exit"  cin>>j;
 while(j)
 {
  cout   cin>>n;
  goods=new struct goodinfo [n+1];
  cout   cin>>M;
  cout   for(i=1;i   {
   goods[i].flag=i;
   cout    cin>>goods[i].w;
   cout    cin>>goods[i].p;
   goods[i].p=goods[i].p/goods[i].w;   //得出物品的效益,重量比
   cout   }
  Insertionsort(goods,n);
  bag(goods,M,n);
  cout to run agian"   cout to exit"   cin>>j;
 }
 system("pause");
 return 0;
}

详解贪心法求解背包问题,爱站技术频道就为大家介绍到这里了,这里类别很多,欢迎大家前来学习。

上一篇:在C++中使用inline关键字的方法

下一篇:浅析二叉树的非递归遍历

您可能感兴趣的文章

相关阅读

热门软件源码

最新软件源码下载