（分数背包）小S有n块蛋糕，编号从1到n。第i块蛋糕的价值是，体积是。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过B。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个a（0<a<l）,并将一块价值是w，体积为v的蛋糕切割成两块，其中一块的价值是a・w,体积是a・v,另一块的价值是（l-a）.w，体 积是（l-a）.v。他可以重复无限次切割操作。现要求编程输出最大可能的价值，以分数的形式输出。比如n=3,B=8,三块蛋糕的价值分别是4、4、2,体积分别是5、3、2。 那么最优的方案就是将体积为5的蛋糕切成两份，一份体积是3，价值是2.4，另一份体积是2，价值是1.6，然后把体积是3的那部分和后两块蛋糕打包进盒子。最优的价值之和是8.4，故程序输出42/5。输入的数据范围为：l≤n≤1000，l≤B≤105，l≤，≤100提示：将所有的蛋糕按照性价比/从大到小排序后进行贪心选择。 试补全程序。
cpp
1#include <iostream>
2using namespace std;
3const int maxn = 1005;
4int n, B, w[maxn], v[maxn];
5int gcd(int u, int v) {
6 if (v == 0)
7 return u;
8 return gcd(v, u % v);
9}
10void print(int w, int v) {
11 int d = gcd(w, v);
12 w = w / d;
13 v = v / d;
14 if (v == 1)
15 printf("%d\n", w);
16 else
17 printf("%d/%d\n", w, v);
18}
19void swap(int &x, int &y) {
20 int t = x; x = y; y = t;
21}
22int main() {
23 scanf("%d %d", &n, &B);
24 for (int i = 1; i <= n; i++) {
25 scanf("%d %d", &w[i], &v[i]);
26 }
27 for (int i = 1; i < n; i++)
28 for (int j = 1; j < n; j++)
29 if (w[j] * v[j + 1] < w[j + 1] * v[j]) {
30 swap(w[j], w[j + 1]);
31 swap(v[j], v[j + 1]);
32 }
33 int curv, curw;
34 if (v[1] <= B) {
35 ③;
36 } else {
37 print(B * w[1], v[1]);
38 return 0;
39 }
40 for (int i = 2; i <= n; i++)
41 if (curv + v[i] <= B) {
42 curv += v[i];
43 curw += w[i];
44 } else {
45 print(④);
46 return 0;
47 }
48 print(⑤);
49 return 0;
50}