【题目描述】
某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1,n2,...,同时每个种类的金属总的价值也不同，分别为v1,v2,...,KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。
【输入样例】
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
思路：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e3 + 10;
struct node {double v;//价值double w;//重量double r;//性价比
}a[N];
bool cmp(node A, node B) {return A.r > B.r;
}
int sum[N];
signed main() {int t; cin >> t;while (t--) {int w, n; cin >> w >> n;for (int i = 1; i <= n; i++) {cin >> a[i].w >> a[i].v;a[i].r = a[i].v / a[i].w; }sort(a + 1, a + n + 1, cmp);double ans = 0;for (int i = 1; i <= n; i++) {//对于第i物品，一定是当前所有物品里性价比最高的if (w >= a[i].w) {//能全装下，全装ans += a[i].v;//总价值+vw -= a[i].w;//重量-w }else {//装不下，尽可能装多ans += a[i].r * w;//用剩余背包容量w*当前物品的单位价值w = 0;//装完了，承重清0break; }}printf("%.2lf\n",ans); }return 0;
}
