金银岛

题目描述

口袋承重上限为 $w$ ，有 $s$ 种金属，第 $i$ 种总重量为 $n_i$ ，总价值为 $v_i$ 。金属可任意分割，且价值与重量成正比。求一次能带走的最大价值。输出保留两位小数。

输入：先给测试组数 $k$ ；每组给出 $w$ 、 $s$ ，以及 $2s$ 个数 $n_1,v_1,\dots,n_s,v_s$ 。 $1\leqslant w,n_i\leqslant 10000$ ， $1\leqslant s\leqslant 100$ 。

思路

每种金属单位重量价值为 $v_i/n_i$ ，是一个常数。按单价从高到低排序后，能装多少就装多少，装不下就切一部分，贪心即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:28
# update_at: 2026-09-30 00:28

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        w = next(data)  # 口袋承重上限
        s = next(data)  # 金属种类数

        metals = []  # (单位重量价值, 总重量)，后面按单价从高到低取
        for _ in range(s):
            n_i, v_i = next(data), next(data)
            metals.append((v_i / n_i, n_i))

        metals.sort(reverse=True)  # 贪心：单价越高越先装

        value = 0.0  # 已装下的总价值
        for unit, weight in metals:
            taken = min(weight, w)     # 这一种最多还能装多少
            value += taken * unit      # 价值和重量成正比
            w -= taken                 # 剩余承重
            if w == 0:
                break                  # 装满了，后面的金属不再看

        out.append(f"{value:.2f}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:57
 * update_at: 2026-10-05 05:58
 */
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

typedef long long ll;

struct Metal {
    ll w;      // 该种金属的总重量
    ll v;      // 该种金属的总价值
    double u;  // 单价 = v / w
};

const int MAXS = 105;
Metal a[MAXS];

bool cmp(Metal x, Metal y) {
    return x.u > y.u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    while (k--) {
        ll w, s;
        cin >> w >> s;
        for (int i = 1; i <= s; i++) {
            cin >> a[i].w >> a[i].v;
            a[i].u = (double)a[i].v / (double)a[i].w;
        }
        sort(a + 1, a + s + 1, cmp);
        double ans = 0;
        ll rest = w;
        for (int i = 1; i <= s && rest > 0; i++) {
            ll take = min(a[i].w, rest);
            ans += take * a[i].u;
            rest -= take;
        }
        cout << fixed << setprecision(2) << ans << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码