NYOJ - 背包问题(贪心)
发布日期:2021-07-01 00:14:53
浏览次数:3
分类:技术文章
本文共 1078 字,大约阅读时间需要 3 分钟。
- 内存限制:64MB 时间限制:3000ms
题目描述:
现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。
输入描述:
第一行输入一个正整数n(1<=n<=5),表示有n组测试数据;随后有n测试数据,每组测试数据的第一行有两个正整数s,m(1<=s<=10);s表示有s个物品。接下来的s行每行有两个正整数v,w。
输出描述:
输出每组测试数据中背包内的物品的价值和,每次输出占一行。
样例输入:
1
3 15 5 10 2 8 3 9
样例输出:
65
解题思路:
为了使放入背包的价值总和最大,首先应该把单位价值最大的物品全部放入背包,然后再放单位价值第二的物品,如此往复,直到背包放满(如果背包容量不足于放该物品的重量,因为是可分割的,故背包有多大放多少).
#include#include using namespace std;struct edge { int v, w;}e[110];int cmp(edge a, edge b) { return a.v > b.v;}int main(){ int t, s, m, ans; cin >> t; while (t--) { ans = 0; cin >> s >> m; for (int i = 0; i < s; i++) cin >> e[i].v >> e[i].w; sort(e, e + s, cmp); for (int i = 0; i < s; i++) { if (m >= e[i].w) { m -= e[i].w; ans += e[i].v * e[i].w; } else { ans += m * e[i].v; break; } } cout << ans << endl; } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84072811 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月29日 07时03分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
消息推送
2019-05-01
智能家居
2019-05-01
酷炫的文件上传技术
2019-05-01
处理键盘输入
2019-05-01
新浪微博授权提示:文件不存在(C8998)的解决方法
2019-05-01
Android开发日常笔记
2019-05-01
androidannotations
2019-05-01
ADB调试工具
2019-05-01
使用Gson解析json数据
2019-05-01
三级缓存
2019-05-01
Gson使用指南
2019-05-01
新闻阅读器频道管理
2019-05-01
开源全能播放器Vitamio的使用
2019-05-01
requestWindowFeature()的应用
2019-05-01
TabLayout属性详解
2019-05-01
Android Fragment嵌套导致的bug
2019-05-01
Android Fragment中嵌套Fragment,不显示view
2019-05-01