CSP-S 提高级 · CSP 2020 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1.（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $a(0<a<1)$，并将一块价值是 $w$，体积为 $v$ 的蛋糕切割成两 块，其中一块的价值是 $a\times w$，体积是 $a\times v$，另一块的价值是$(1-a)\times w$，体积是 $(1-a)\times v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 $n=3,B=8$，三块蛋糕的价值分别是 $4,4,2$，体积分别是 $5,3,2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 $8.4$，故程序输出 $\dfrac{42}{5}$。

输入的数据范围为：$1\leq n\leq 1000$，$1\leq B\leq 10^5$，$1\leq w_i,v_i\leq 100$。

提示：将所有的蛋糕按照性价比 $\dfrac{w_i}{v_i}$ 可从大到小排序后进行贪心选择。

试补全程序。

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
} 

void p

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题是经典的分数背包问题，核心在于贪心策略：按性价比（价值/体积）从高到低排序，能整块拿就整块拿，拿不下就切一部分填满。排序时千万别用浮点除法，要用交叉相乘比较，否则精度不够会翻车。

学生最容易栽跟头在两个地方：一是排序条件写反或者用了浮点运算导致比较错误；二是切割那一步的分子分母凑不对，把“剩余体积乘单价”和“已装价值”混成整数加法，忽略了分母必须统一成当前物品的体积。另外，输出格式里如果忘记约分，或者 v=1 时还强行输出分数，也会丢分。

考点与概念

这道题考查的是贪心算法在分数背包问题上的应用。分数背包和 0-1 背包最大的区别在于：分数背包允许切割物品，因此贪心策略（按性价比排序）一定是最优的；而 0-1 背包只能整拿或整舍，贪心就不行了。

性价比就是单位体积的价值，即 $w_i/v_i$。我们要把性价比高的往盒子里塞。为了编程方便且避免浮点误差，比较两个分数 $rac{w_j}{v_j}$ 和 $rac{w_{j+1}}{v_{j+1}}$ 时，直接交叉相乘： $$rac{w_j}{v_j} < rac{w_{j+1}}{v_{j+1}} \ \iff w_j \times v_{j+1} < w_{j+1} \times v_j$$ 这样全是整数运算，绝对准确。

程序逻辑梳理

程序整体分三步走： 1. 排序：用冒泡把蛋糕按性价比从大到小排好。 2. 处理第一个：如果第一个蛋糕体积 $v_1$ 能塞进盒子（$v_1 \le B$），就整个拿走，作为初始已装体积 $curV$ 和价值 $curW$；否则盒子只能装下 $B/v_1$ 份这个蛋糕的碎片，直接输出结果并结束。 3. 依次贪心：从第二个开始，能整块拿就整块拿，拿不下就切一部分填满剩余空间 $B-curV$，然后输出。