题目信息

题目类型
提高级
题目年份
2020
题目题型
单选题
关 键 词
分数背包

题目题干

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

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

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

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

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

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

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

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

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

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

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

④ 处应填( )edk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

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

答案解析

相关题目

第38题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第37题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第36题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第35题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第34题 (分数背包)小 S 有 n 块蛋糕,编号从 1 到 n。第 i 块蛋糕的价值是 wi,体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕,也就是说装入盒子的蛋糕的体积总和不能超过 B。
第33题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2
第32题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2
第31题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2
第30题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2
第29题 #include <iostream>  #include <queue>  using namespace std;      const int maxl = 2

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢