第34题 （分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。

第34题clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

现要求编程输出最大可能的价值，以分数的形式输出。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试补全程序。clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. 第34题 
2.  
3. （分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。 
4.  
5. 他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。 
6.  
7. 为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。 
8.  
9. 现要求编程输出最大可能的价值，以分数的形式输出。 
10.  
11. 比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。 
12.  
13. 那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。 
14.  
15. 输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。 
16.  
17.  
18. #include <cstdio>  
19. using namespace std;  
20.    
21. const int maxn = 1005;  
22.    
23. int n, B, w[maxn], v[maxn];  
24.    
25. int gcd(int u, int v) {  
26.     if (v == 0)  
27.         return u;  
28.     return gcd(v, u % v);  
29. }  
30.    
31. void print(int w, int v) {  
32.     int d = gcd(w, v);  
33.     w = w / d;  
34.     v = v / d;  
35.     if (v == 1)  
36.         printf("%d\n", w);  
37.     else  
38.         printf("%d/%d\n", w, v);  
39. }  
40.    
41. void swap(int &x, int &y) {  
42.     int t = x; x = y; y = t;  
43. }  
44.    
45. int main() {  
46.     scanf("%d %d", &n, &B);  
47.     for (int i = 1; i <= n; i ++) {  
48.         scanf("%d%d", &w[i], &v[i]);  
49.     }  
50.     for (int i = 1; i < n; i ++)  
51.         for (int j = 1; j < n; j ++)  
52.             if ( ① ) {  
53.                 swap(w[j], w[j + 1]);  
54.                 swap(v[j], v[j + 1]);  
55.             }  
56.     int curV, curW;  
57.     if ( ② ) {  
58.         ③  
59.     } else {  
60.         print(B * w[1], v[1]);  
61.         return 0;  
62.     }  
63.    
64.     for (int i = 2; i <= n; i ++)  
65.         if (curV + v[i] <= B) {  
66.             curV += v[i];  
67.             curW += w[i];  
68.         } else {  
69.             print( ④ );  
70.             return 0;  
71.         }  
72.     print( ⑤ );  
73.     return 0;  
74. }  

① 处应填（ ）clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A. w[j] / v[j] < w[j + 1] / v[j + 1]clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B. w[j] / v[j] > w[j + 1] / v[j + 1]clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C. v[j] * w[j + 1] < v[j + 1] * w[j]clt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
D. w[j] * v[j + 1] < w[j + 1] * v[j]