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}$ 可从大到小排序后进行贪心选择。

试补全程序。

1#include <cstdio>2using namespace std;3 4const int maxn = 1005;5 6int n, B, w[maxn], v[maxn];7 8int gcd(int u, int v) {9    if (v == 0)10        return u;11    return gcd(v, u % v);12}13 14void print(int w, int v) {15    int d = gcd(w, v);16    w = w / d;17    v = v / d;18    if (v == 1)19        printf("%d\n", w);20    else21        printf("%d/%d\n" w, v);22}23void swap(int &x, int &y) {24    int t = x; x = y; y = t;25}26 27int main() {28    scanf("%d %d" &n, &B);29    for (int i = 1; i <= n; i ++) {30        scanf("%d %d", &w[i], &v[i]);31    }32    for (int i = 1; i < n; i ++)33        for (int j = 1; j < n; j ++)34            if (①) {35                swap(w[j], w[j + 1]);36                swap(v[j], v[j + 1]);37            }38    int curV, curW;39    if  (②) {40        ③41    } else {42        print(B * w[1] , v[1]);43        return 0;44    }45    for (int i = 2; i <= n; i ++)46        if (curV + v[i] <= B) {47            curV += v[i];48            curW += w[i];49        } else {50            print (④);51            return 0;52        }53    print(⑤);54    return 0;55}