金银岛（信息学奥赛一本通 - T1225）

题目描述 某天 KID 利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，

KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属，但是他只带着一个口袋，口袋至多只能装重量为 w 的物品。

岛上金属有 s 个种类, 每种金属重量不同，分别为 n1, n2, …, ns，同时每个种类的金属总的价值也不同，分别为 v1, v2, …, vs。

KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。

注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

输入格式 第 1 行是测试数据的组数 k，后面跟着 k 组输入， 每组测试数据占 3 行，

第 1 行是一个正整数 w，表示口袋承重上限。 第 2 行是一个正整数 s，表示金属种类。 第 3 行有 2s 个正整数，分别为 n1, v1, n2, v2, …, ns, vs 分别为第一种，第二种，…，第 s 种金属的总重量和总价值

输出格式 k 行，每行输出对应一个输入，输出应精确到小数点后 2 位。

输入样例 2 50 4 10 100 50 30 7 34 87 100 10000 5 1 43 43 323 35 45 43 54 87 43

输出样例 171.93 508.00

数据范围 1 ≤ s ≤ 100 1 ≤ w ≤ 10000 1 ≤ ni ≤ 10000, 1 ≤ vi ≤ 10000

题解 贪心：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int T;
int n, m;

struct thing
{
          
   
	int v, w;
	double x;
}s[N];

bool cmp(thing a, thing b)
{
          
   
	return a.x > b.x;
}

int main()
{
          
   
	cin >> T;
	
	while(T --)
	{
          
   
		cin >> m >> n;
		for (int i = 1; i <= n; i ++)
		{
          
   
		 	cin >> s[i].v >> s[i].w;
		 	s[i].x = 1.0 * s[i].w / s[i].v;
		}
		
		sort(s + 1, s + 1 + n, cmp);
		
		double ans = 0;
		for (int i = 1; i <= n; i ++)
			if(m >= s[i].v)
			{
          
   
				m -= s[i].v;
				ans += s[i].w;
			}
			else
			{
          
   
				ans += s[i].x * m;
				break;
			}
		
		printf("%.2f
", ans);
	}
	
	return 0;
}