洛谷——部分背包问题【贪心】

洛谷P2240

样例：

输入：
4 50
10 60
20 100
30 120
15 45
输出：
240.00

思路：与动态规划的背包问题不同，此处的金币是可以随意分割的，我们可以运用贪心，优先选取最合适的金币堆。怎么优先选择呢？？题中说道：“分割完的金币重量价值比（也就是单位价格）不变”。所以可以优先选择单位价格大的金币堆。
AC代码：

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int m,v;
}a[105];
bool cmp(const Node &a,const Node &b)
{
	//按单位价格降序排序，交叉相乘避免精度损失
	//a.v/a.m > b.v/b.m  ---->a.v*b.m > b.v*a.m
	return a.v*b.m > b.v*a.m;	
}
int main()
{
	int n,t;
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;i++)
		scanf("%d%d",&a[i].m,&a[i].v);
	sort(a,a+n,cmp);//按单位价格降序排序
	double sum=0;
	for(int i=0;i<n;i++)
	{
		if(t>=a[i].m)//背包能放下整堆金币
		{
			t-=a[i].m;//背包容量减少
			sum+=a[i].v;
		}
		else//不能放下整堆金币
		{
			sum+=1.0*a[i].v/a[i].m*t;//将背包装满
			break;
		}
	}
	printf("%.2f\n",sum);
	return 0;
}