CSP-S 2020 第一轮 第34题：完善程序（第 19 题）第 1 空

题目

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 print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n" w, v);
}
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d" &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if (①) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if  (②) {
        ③
    } else {
        print(B * w[1] , v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print (④);
            return 0;
        }
    print(⑤);
    return 0;
}

①处应填（ ）

选项

• A. w[j] / v[j] < w[j+1] / v[j+1]
• B. w[j] / v[j] > w[j +1] / v[j+1]
• C. v[j] * w[j+1] < v[j+1] * w[j]
• D. w[j] * v[j+1] < w[j+1] * v[j]

答案

D

题解

选 D。

题目要求按性价比 \(\frac{w_i}{v_i}\) 从大到小排序。冒泡排序时，如果左边蛋糕的性价比比右边低，就应交换：

\[ \frac{w[j]}{v[j]}<\frac{w[j+1]}{v[j+1]} \]

因为体积都为正数，交叉相乘可得：

\[ w[j]\times v[j+1]<w[j+1]\times v[j] \]

对应选项 D： ``cpp w[j] * v[j+1] < w[j+1] * v[j] ``

A 为什么不对？ w、v 都是整数，C++ 的整数除法会舍去小数。例如 4 / 3 和 3 / 2 都得到 1，无法正确比较实际性价比。交叉相乘可以避免这个问题。