首页 > 代码库 > 贪心思想之部分背包算法

贪心思想之部分背包算法

2024-07-28 16:19:42   217人阅读

贪心的思想：通过每一步都找最优解决问题。因为每一步最优，最后是最优的概率很大。

部分背包的思想就是：把最值钱的往包里装，装得越多越好。可见设计算法的人好贪啊，嘿嘿~

样例：

n种东西，重量是Mi,价值是Vi，单价就是两者之比Pi。C为小包包的容量。最后算出的结果是对应取Xi放到包中。

代码如下：

#include<iostream>using namespace std;float *m,*v,*p,*x;float c;//背包容量int n,h;void TaskInitial();void result_out();void Greedy_beibao();void calculate_p();int find_next_big_p(int);void load_beibao(int);int main(){		TaskInitial();	Greedy_beibao();	result_out();	return 0;}/*基本输入输出*/void TaskInitial(){	cin>>c;//背包容量	cin>>n;//物品种类	m=(float *)malloc(n*sizeof(float));//存物品质量	v=(float *)malloc(n*sizeof(float));//存物品对应总价值	p=(float *)malloc(n*sizeof(float));//存放物品单价	x=(float *)malloc(n*sizeof(float));//存 放入背包的物品的数量	for(int i=0;i<n;i++)		{		cin>>*(m+i)>>*(v+i);		*(p+i)=(*(v+i))/(*(m+i));		*(x+i)=0;	}}void result_out(){	float totalval=0;	for(int i=0;i<n;i++)	{		cout<<*(x+i)<<endl;		totalval+=((*(v+i))/(*(m+i)))*(*(x+i));	}	cout<<"总价值："<<totalval<<endl;}/*贪心算法*/void Greedy_beibao(){	h=1;		load_beibao(find_next_big_p(h));}int find_next_big_p(int i){	float tempdata;	int k=0;	for(int j=0;j<n;j++)		if(*(p+j)>*(p+k))			k=j;	*(p+k)=0;	return k;}void load_beibao(int k) {	if(c<=*(m+k))		*(x+k)=c;	else	{		*(x+k)=*(m+k);		c-=*(m+k);		h++;		if(h<=n)			load_beibao(find_next_big_p(h));	}}

　　测试一下吧：

部分背包问题暂时搞定，继续！

贪心思想之部分背包算法


联系
我们