题目信息

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

题目题干

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

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

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

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

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

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

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

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

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

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

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

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

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

答案解析

相关题目

第39题 (最优子序列)取 m = 16,给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x,定义其分值 w(x) 为x+popcnt(x),其中 popcnt
第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

提示声明

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

猜你喜欢