贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。
应用: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:最优子结构性质:某个...
为C语言课程设计写的基于贪心法的背包问题,包含全部4种贪心策略
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
算法设计实验报告,包括:贪心法求解背包问题的基本思想、动态规划法求解0/1背包问题的基本思想及各自的时间复杂度分析,两种问题的区别,C++实现代码,运行截图,实验心得。
用贪心法解决背包问题的源代码,在vc++环境下也可以运行
贪心算法 背包问题 c语言 绝对无误 运行成功
背包问题的贪心算法实现,简答易懂 if(m>=weight[i]) { value=value+profit[i]; m-=weight[i]; s[i]=1; } else if(m!=0) { value=value+profit[i]*(1.0*m/weight[i]); s[i]=1.0*m...
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
。。。
背包问题的贪心法求解.exe
0-1背包问题(贪心算法)C语言源程序. 物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。
贪心问题中有很多典型的例子,此次背包问题,助大家理解该算法
1) 动态规划法求解问题的一般思路,动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。 2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现...
在背包问题中,取得最优解一直是解决背包问题的最终目的,就贪心算法的动态规划关系以及方案在解决背包问题上作比较,但贪心法在什么时候都能取到最优解并无一般结论,而对于普通背包问题我们却有一个完美的结果——贪心...
分支限界法求解01背包 分支限界法、回溯法、贪心算法求解01背包python源码.zip分支限界法、回溯法、贪心算法求解01背包python源码.zip分支限界法、回溯法、贪心算法求解01背包python源码.zip分支限界法、回溯法、...
通过C++实现的贪婪算法处理背包问题的程序,有注释,希望对大家有所帮助!
0-1背包问题-贪心法和动态规划法求解1.pdf0-1背包问题-贪心法和动态规划法求解1.pdf
算法设计实验报告,包括:蛮力、动态规划、回溯、分支限界四种算法求解0/1背包问题的基本思想、时间复杂度分析,C++实现代码,运行结果截图,实验心得。
给定n种物品和一个背包,物品I的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?