P4787 可分割背包问题（基础）

解题思路

第一步，读懂题目。 冒险家的背包容量是 g 升，山洞里有 n 种财宝，第 i 种有 a_i 升、总价值 b_i。财宝可以按“1 升”为单位分割装进背包，问背包最多能装价值多少的财宝。

第二步，想到贪心。 因为财宝可以分割，我们当然要先装“每升价值最高”的财宝，再装次高的，这样同样多的容量能装到最多的总价值。

第三步，计算每升价值。 第 i 种财宝每升的价值 = b_i 除以 a_i。先把所有财宝按每升价值从高到低排序。

第四步，依次装进背包。 从每升价值最高的开始：如果这种财宝全部装得下（a_i 不超过剩余容量），就全部装进去，总价值加上 b_i，剩余容量减去 a_i；如果装不完，就只能装剩余容量那么多升，总价值加上 每升价值 乘 剩余容量，然后背包就满了，结束。

第五步，保留两位小数。 最后结果要保留 2 位小数，用 double 类型保存总价值，用 printf 输出 %.2lf。

第六步，举一个例子。 容量 10 升，5 种财宝的每升价值分别是 1、2、4、3、7.5。先装每升 7.5 的 2 升（价值 15），再装每升 4 的 3 升（价值 12），再装每升 3 的 5 升（价值 15），一共 42.00。

第七步，注意背包恰好装满的情况。 装到最后一种财宝时，如果背包的剩余容量比这种财宝的总升数少，就只装剩余容量那么多升，总价值加上 每升价值 乘 剩余容量，背包正好装满就结束。如果所有财宝都装完了背包还没满，那也没关系，因为能装进背包的财宝就这么多，已经是最优的了。

参考代码

// 可分割背包问题：财宝可以按单位分割，把每升价值最高的财宝优先装进背包，直到装满容量
#include <iostream>
#include <algorithm>
using namespace std;

struct Treasure {
    int quantity;  // 这种财宝的总升数
    int value;     // 这种财宝的总价值
    double unit;   // 每升的价值 = value / quantity
};

Treasure arr[105];

// 比较函数：每升价值高的财宝排在前面
bool cmp(const Treasure &a, const Treasure &b) {
    return a.unit > b.unit;
}

int main() {
    int n, g;
    scanf("%d%d", &n, &g);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &arr[i].quantity, &arr[i].value);
        arr[i].unit = (double)arr[i].value / arr[i].quantity;
    }
    sort(arr, arr + n, cmp);
    double total = 0;
    int left = g; // 背包还剩下的容量
    for (int i = 0; i < n; i++) {
        if (left <= 0) break;
        if (arr[i].quantity <= left) {
            // 这种财宝全部装得下
            total += arr[i].value;
            left -= arr[i].quantity;
        } else {
            // 装不下全部，只能装剩余容量那么多，按每升价值折算
            total += arr[i].unit * left;
            left = 0;
        }
    }
    printf("%.2lf\n", total);
    return 0;
}

复杂度分析

排序需要 O(n log n)，贪心扫描一遍是 O(n)，总时间复杂度 O(n log n)。题目中 n 小于 100，运算量很小。空间 O(n)，存每种财宝的数量、价值和每升价值。