用贪心法求解背包问题的解决方法
更新时间:2020年4月25日 17:47 点击:1722
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。
应用:
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<=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];
}
}//按物品效益,重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
float cu;
int i,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M; //背包剩余容量
for(i=1;i<n;i++)
{
if(goods[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<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
cout<<"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
int main(void)
{
cout<<"|--------运用贪心法解背包问题---------|"<<endl;
cout<<"|-------------------------------------|"<<endl;
int i,j,n;
float M;
goodinfo *goods; //定义一个指针
cout<<"press <1> to run the program"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
while(j)
{
cout<<"请输入物品的总数量:";
cin>>n;
goods=new struct goodinfo [n+1];
cout<<"请输入背包的最大容量:";
cin>>M;
cout<<endl;
for(i=1;i<=n;i++)
{
goods[i].flag=i;
cout<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w; //得出物品的效益,重量比
cout<<endl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
system("pause");
return 0;
}
应用:
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<=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];
}
}//按物品效益,重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
float cu;
int i,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M; //背包剩余容量
for(i=1;i<n;i++)
{
if(goods[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<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
cout<<"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
int main(void)
{
cout<<"|--------运用贪心法解背包问题---------|"<<endl;
cout<<"|-------------------------------------|"<<endl;
int i,j,n;
float M;
goodinfo *goods; //定义一个指针
cout<<"press <1> to run the program"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
while(j)
{
cout<<"请输入物品的总数量:";
cin>>n;
goods=new struct goodinfo [n+1];
cout<<"请输入背包的最大容量:";
cin>>M;
cout<<endl;
for(i=1;i<=n;i++)
{
goods[i].flag=i;
cout<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w; //得出物品的效益,重量比
cout<<endl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
system("pause");
return 0;
}
相关文章
- 这篇文章主要介绍了C#使用动态规划解决0-1背包问题,实例分析了C#动态规划算法的实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 贪心算法 WOODEN STICKS 实例代码,需要的朋友可以参考一下...2020-04-25
- 这篇文章主要介绍了Python 经典贪心算法之Prim算法案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-09-06
- 这篇文章主要介绍了C++ 搬水果贪心算法实现代码的相关资料,需要的朋友可以参考下...2020-04-25
- 背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个物体再继续细分的情况。...2020-06-25
- 本篇文章是对用贪心法求解背包问题的解决方法进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C#使用回溯法解决背包问题,实例分析了背包问题的描述及C#解决方法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C++动态规划之背包问题解决方法,实例分析了背包问题的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了贪心算法的C语言实现与运用详解,运用么,就是文中所附的ACM练习题,哈哈:D需要的朋友可以参考下...2020-04-25
- 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。这篇文章主要介绍了C++贪心算法实现活动安排问题,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言基于贪心算法解决装箱问题的方法,简单描述了装箱问题,并结合实例形式给出了C语言使用贪心算法解决贪心问题的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了关于背包问题的一些理解和应用,本文可以说是背包问题九讲的补充、读后感,需要的朋友可以参考下...2020-04-25