csp信奥赛C++高频考点专项训练之贪心算法 --【部分背包问题】：部分背包问题

csp信奥赛C高频考点专项训练之贪心算法 --【部分背包问题】部分背包问题#### 题目描述阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N ( N ≤ 100 ) N(N \le 100)N(N≤100)堆金币第i ii堆金币的总重量和总价值分别是m i , v i ( 1 ≤ m i , v i ≤ 100 ) m_i,v_i(1\le m_i,v_i \le 100)mi​,vi​(1≤mi​,vi​≤100)。阿里巴巴有一个承重量为T ( T ≤ 1000 ) T(T \le 1000)T(T≤1000)的背包但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。请问阿里巴巴最多可以拿走多少价值的金币输入格式第一行两个整数N , T N,TN,T。接下来N NN行每行两个整数m i , v i m_i,v_imi​,vi​。输出格式一个实数表示答案输出两位小数。输入输出样例 1输入 14 50 10 60 20 100 25 100 15 45输出 1240.00思路分析这是一个典型的部分背包问题也称为分数背包问题。与 0/1 背包不同金币可以任意分割因此最优策略是优先选择单位价值价值/重量最高的金币堆直到背包装满。具体步骤计算每堆金币的单位价值avg v / m。将所有金币堆按avg降序排序。遍历排序后的金币堆如果当前堆可以全部装入则全部拿走背包容量减少总价值增加。否则只装入剩余容量所能容纳的部分按比例计算价值然后结束。输出总价值保留两位小数。时间复杂度排序 O(N log N)遍历 O(N)满足 N ≤ 100 的约束。代码实现#includebits/stdc.husingnamespacestd;structnode{doublem,v,avg;// 重量、总价值、单位价值}a[110];boolcmp(node x,node y){returnx.avgy.avg;// 按单位价值降序排序}intmain(){intn,t;// n:堆数, t:背包容量cinnt;for(inti1;in;i){cina[i].ma[i].v;a[i].avga[i].v/a[i].m;// 计算单位价值}sort(a1,an1,cmp);// 贪心排序doubleans0;// 记录最大价值for(inti1;int0;i){if(ta[i].m){// 能全部装下ansa[i].v;t-a[i].m;}else{// 只能装部分anst*a[i].avg;// 按比例计算价值t0;// 背包已满}}printf(%.2lf\n,ans);// 输出两位小数return0;}功能分析输入处理读取金币堆数n和背包容量t再依次读取每堆的重量m和价值v。单位价值计算avg v / m用于贪心决策。排序按单位价值从高到低排列确保优先取“性价比”最高的金币。贪心装载若当前堆能完全装入则全部拿走。否则只取剩余容量对应的部分重量 × 单位价值背包随即装满。输出使用printf格式化输出两位小数的最大价值。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、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.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、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.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}