【洛谷 P2240】【深基12.例1】部分背包问题题解（贪心算法）

创始人

2025-05-31 18:43:21

【深基12.例1】部分背包问题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100)N(N \le 100)N(N≤100) 堆金币，第 iii 堆金币的总重量和总价值分别是 mi,vi(1≤mi,vi≤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,TN,TN,T。

接下来 NNN 行，每行两个整数 mi,vim_i,v_imi,vi。

输出格式

一个实数表示答案，输出两位小数

样例 #1

样例输入 #1

样例输出 #1

240.00

思路

按金币单价对每堆金币从大到小排序，然后按金币单价将一堆堆金币放入背包。当若下一堆金币放不下背包时，计算背包剩余空间，将下一堆金币分割后，得到与背包剩余空间相等的金币重量的一小堆金币，用其装满背包。

AC代码

#include 
#include 
#include 
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 100005;struct S{int m;double v;
}g[maxn];bool cmp(S x, S y){return (x.v / x.m) > (y.v / y.m);
}int main(){int n, t;cin >> n >> t;for(int i = 0; i < n; i++){cin >> g[i].m >> g[i].v;}sort(g, g + n, cmp);struct S h = {0, 0};int ii = 0;while(h.m + g[ii].m <= t && ii < n){h.m += g[ii].m;h.v += g[ii].v;ii++;}if(h.m < t && ii < n){int l = t - h.m;h.v += l * g[ii].v / g[ii].m;}cout << setiosflags(ios::fixed) << setprecision(2) << h.v << endl;return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：今年第一季度100元以下产品的收入为何下滑？金徽酒回应金徽酒今年年报如何金徽酒今年放慢增速

下一篇：jpg格式图片打不开怎么办

热门资讯

欧佩克+同意7月再增产41.1... 为了增产惩罚超产国并争夺市场份额，欧佩克+连续第三个月大幅增产，美国页岩油生产商或首当其冲，美油一度...

更名！“天府证券”来了天府证... 【导读】宏信证券更名为天府证券中国基金报记者吴君这家券商，历史上第二次更名。5月末，工商信息显示，...

两家A股公司，收终止上市决定 ... 又有两家A股上市公司收到股票终止上市决定，6月10日进入退市整理期。*ST鹏博(600804)公告称...

瑞幸降价迈入“6块9”时代？瑞... 说起最近几年的咖啡茶饮市场，相信每个人都不会陌生，各家咖啡茶饮企业的各种降价消息是此起彼伏，就在最近...

主次节奏：6.1黄金 - 每周... 本文每周初更新发布梳理各级别走势分析和预期主次节奏：做有品质的三方服务黄金月线图（超长线）月线图...

超400亿资金狂涌！这类ETF... 债券ETF市场持续扩容。今年以来，债券市场表现震荡，债券类基金回报远不及预期，但这并未妨碍债券型ET...

坚定信心行稳致远（记者手记）侯琳良最近一段时间，海尔集团上世纪90年代投资制作的《海尔兄弟》动画片，在多个视频平台上线高清重制...

世纪大辩论2——哈耶克与凯恩斯... 本来节后决定启动一个项目，但家里临时有事，需要陪家人去一趟北京，节后拉群的事，因此要推迟一周左右（具...

4月广州消费品市场表现强劲 1-4月，随着消费品以旧换新等促消费政策持续发力和各类会展活动陆续开展，政策相关消费快速增长，升级类...

金价，又跌了！人民财讯5月31日电，5月30日，COMEX黄金期货收跌0.92%，报3313.1美元/盎司。从高...

10万吨改性项目！巴斯夫、金发... 【DT新材料】获悉，6月3日，沪市主板新股海阳科技将启动申购，上市在即！资料显示，海阳科技前身为南...

湾财周报|大事记比亚迪驳斥“... 一周大事记（5月26日-6月1日）头条比亚迪驳斥！长城“车圈恒大论”是行业警示还是危言耸听？...

通源石油跌1.96%，成交额1... 5月30日，通源石油跌1.96%，成交额1.03亿元，换手率4.40%，总市值23.54亿元。异动...

中国邮储银行浙江分行2025校... 点这里 ↑ 老满说高考作者 l 老满生涯规划师l 升学顾问l 拆书家这是老满说高考公众号的...

公募基金规模首次突破33万亿元... 每经记者：肖芮冬每经编辑：叶峰天赐良基日报第654期一、今日基金新闻速览 1、华润元大基金贾...

湾财周报大事记比亚迪驳斥“... 一周大事记（5月26日-6月1日）头条比亚迪驳斥！长城“车圈恒大论”是行业警示还是危言耸听？近日，关...

EL表达式JSTL标签库 EL表达式 EL：Expression Language 表达式语言 ...

关于测试，我发现了哪些新大陆关于测试平常也只是听说过一些关于测试的术语，但并没有使用过测试工具。偶然看到编程老师...

工信部、中汽协紧急发声！汽车“... 文/刘育英新一轮汽车价格战再起。近日，工信部、中汽协纷纷发声表示反对。工业和信息化部表示，将加大对汽...

3 ROS1通讯编程提高(1) 3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...

募资39亿，全亏光了，账上不到... 关于天然气，用户的感觉是价格一直在上涨，但很奇怪，不管怎么涨，天然气企业仍然亏，还亏得一塌糊涂。这是...

资阳房产评估公司这是(tel-15828298733)整理的信息，希望能帮助到大家在当今社会，随着经济的发展和城...

华桥汇利（中国）投资基金管理有... 今年第一季度，美国企业利润出现大幅下降，且面临着来自关税上升的持续压力，这一局面可能会在今年进一步加...

ESG 报告合规与鉴证：全球政... 在当下全球经济格局里，ESG（环境、社会和公司治理）已然成为衡量企业可持续发展能力的关键指标。随着全...

【Unity 手写PBR】Bu... 写在前面前期积累： GAMES101作业7提高-实现微表面模型你需要了解的知识【技...

与锤巨子生物的大嘴博士持股同一... 医美龙头巨子生物“成分争议”风波持续发酵。日前，美妆博主大嘴博士（香港大学化学博士郝宇）发文，质疑巨...

Linux之进程间通信目录进程间通信介绍一、为什么要进行进程间通信？二、进程间通信目的三、进程间通信...

从“造城”到“留客”，文旅局长... 你有没有刷到最近各地文旅局局长全体“尬舞”的视频？领导们放下架子开始跳魔性舞蹈，这场舞的背后啊，可不...

Hazel引擎学习（十一）我自己维护引擎的github地址在这里，里面加了不少注释，有需要的可以看...

孩子的教育金，分享3个「有效」... 点击 “简七读财” ，发送消息“ 理财小工具 ”免费领取“40个赚钱工具资源包”晚上好，我是简七编...

【洛谷 P2240】【深基12.例1】部分背包问题 题解（贪心算法）