2020年信奥赛C提高组csp-s初赛真题及答案解析完善程序第1题第1题分数背包小 S 有 n 块蛋糕编号从 1 到 n。第 i块蛋糕的价值是w i w_iwi体积是v i v_ivi。他有一个大小为 B的盒子来装这些蛋糕也就是说装入盒子的蛋糕的体积总和不能超过 。他打算选择一些蛋糕装入盒子他希望盒子里装的蛋糕的价值之和尽量大。为了使盒子里的蛋糕价值之和更大他可以任意切割蛋糕。具体来说他可以选择一个 a(0a1)并将一块价值是 w体积为 v的蛋糕切割成两块其中一块的价值是 a×w体积是 a×v另一块的价值是(1−a)×w体积是 (1−a)×v。他可以重复无限次切割操作。现要求编程输出最大可能的价值以分数的形式输出。比如 n3,B8三块蛋糕的价值分别是 4,4,2体积分别是 5,3,2。那么最优的方案就是将体积为 5的蛋糕切成两份一份体积是 3价值是 2.4另一份体积是 2价值是 1.6然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4故程序输出42 5 \frac{42}{5}542。输入的数据范围为1≤n≤10001≤B≤1051≤w i , v i w_i,v_iwi,vi≤100。提示将所有的蛋糕按照性价比w i v i \frac{w_i}{v_i}viwi可从大到小排序后进行贪心选择。试补全程序。#includecstdiousingnamespacestd;constintmaxn1005;intn,B,w[maxn],v[maxn];intgcd(intu,intv){if(v0)returnu;returngcd(v,u%v);}voidprint(intw,intv){intdgcd(w,v);ww/d;vv/d;if(v1)printf(%d\n,w);elseprintf(%d/%d\nw,v);}voidswap(intx,inty){inttx;xy;yt;}intmain(){scanf(%d %dn,B);for(inti1;in;i){scanf(%d %d,w[i],v[i]);}for(inti1;in;i)for(intj1;jn;j)if(①){swap(w[j],w[j1]);swap(v[j],v[j1]);}intcurV,curW;if(②){③}else{print(B*w[1],v[1]);return0;}for(inti2;in;i)if(curVv[i]B){curVv[i];curWw[i];}else{print(④);return0;}print(⑤);return0;}①处应填 A.w[j] / v[j] w[j1] / v[j1]B.w[j] / v[j] w[j 1] / v[j1]C.v[j] * w[j1] v[j1] * w[j]D.w[j] * v[j1] w[j1] * v[j]②处应填 A.w[1] BB.v[1] BC.w[1] BD.v[1] B③处应填 A.print(v[1],w[1]); return 0;B.curV 0; curW 0;C.print(w[1], v[1]); return 0;D.curV v[1]; curW w[1];④处应填 A.curW * v[i] curV * w[i], v[i]B.(curW - w[i]) * v[i] (B - curV) * w[i], v[i]C.curW v[i], w[i]D.curW * v[i] (B - curV) * w[i], v[i]⑤处应填 A.curW,curVB.curW, 1C.curV, curWD.curV, 1答案及题解①处应填 D因为需要按性价比从大到小排序比较时用交叉乘法避免浮点误差。②处应填 B判断第一个蛋糕的体积是否不超过背包容量若是则先完整取走。③处应填 D初始化当前已取体积和价值为第一个蛋糕的完整值。④处应填 D计算取部分蛋糕时的总价值分子分母为当前蛋糕的体积。⑤处应填 B所有蛋糕完整取完后输出总价值分母为1。专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}