【算法竞赛】贪心算法：01部分背包问题

问题描述：
有 n 个物体，第 i 个物体的重量为 wi,价值为 vi。在总重量不超过 C 的情况下，让总价值尽量高。每一个物体都可以只取走一部分，价值和重量按比例计算。
解题思路：
优先拿“价值除以重量的值”（性价比）最高的，直到重量和正好为 C。
由于可以只取一部分，所以一定可以取到重量和正好为 C；并且只有最后取的物体是部分取（或者不取），在其之前取的物体都是全部取走。

例题：老鼠和猫的交易
题目描述：
有一只老鼠很喜欢奶酪，但是奶酪被分别放在N个房间里，而且这些房间都有一只猫咪看守，现在它准备和猫咪们做个交易。它有M磅的猫食，想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪 J[i] 磅，同时猫咪需要 F[i] 磅的食物，如果老鼠给猫咪 F[i] (a)% 的猫食，那么它就可以得到J[i] (a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数，那老鼠怎样才能换得最多的奶酪呢？

输入
第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求量）。

输出
输出老鼠得到的最多的奶酪数，保留三位小数。

数据范围：
第一行输入两个正整数M和N（M和N不大于10000），后面跟N行（每个房间的奶酪数和猫食的需求量）。

AC代码：

#include
#include
using namespace std;
struct node{
	double get,cost,value;
}a[10000];

bool cmp(node x,node y){
	return x.value>y.value;
}

int main (){
	int food,room;
	int i;
	double sum;
	while(scanf("%d%d",&food,&room)==2){
		if(food==-1&&room==-1)
			break;
		else{
			sum=0;
			for(i=0;ia[i].cost){
					sum+=a[i].get;
					food-=a[i].cost;
				}
				else{
					sum+=food*a[i].get/a[i].cost;
					break;
				}
			}
			sum=(int)(sum*1000+0.5)/1000.0;
			//手动四舍五入 
			printf("%.3lf\n",sum);	 
		}
	}
	return 0;
} 

注：手动四舍五入是为了避免某些测试用例的数据在 printf 格式化输出时出现误差。
参考：[https://blog.csdn.net/weixin_44841943/article/details/119836060]
解决方法：
ans=(int)(ans*10^k + 0.5)/10^k;