【例85.1】 金银岛

解题思路

金属可分割，按单位重量价值v/w降序装入。每种拿min(剩容量,该种总重)，收益增加拿取重量×单价，直到容量满或无金属。

正确性说明

若已装低单价金属而高单价仍有余量，用等重高单价替换可提高价值。最优方案必先装满更高单价，再考虑更低单价，因此贪心最优。

易错点

这是分数背包，不能用01背包；输出两位小数。

复杂度

每组时间O(s log s)，空间O(s)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    while (k--) {
        double W;
        int s;
        cin >> W >> s;
        vector<pair<double, double>> a(s);
        for (auto &p : a)
            cin >> p.first >> p.second;
        sort(a.begin(), a.end(),
             [](const pair<double, double> &x, const pair<double, double> &y) {
                 return x.second * y.first > y.second * x.first;
             });
        double ans = 0;
        for (auto p : a) {
            double take = min(W, p.first);
            ans += take * p.second / p.first;
            W -= take;
            if (W <= 0)
                break;
        }
        cout << fixed << setprecision(2) << ans << "\n";
    }
    return 0;
}