NYOJ - 背包问题(贪心)
发布日期:2021-07-01 00:14:53
浏览次数:2
分类:技术文章
本文共 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月17日 18时55分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
svn add 输出 A (bin)
2019-05-01
python传递中文参数编码问题
2019-05-01
Linux主机间建立信任关系,无ssh密码登陆主机的问题
2019-05-01
C/C++ 程序的性能分析工具 google-perftools
2019-05-01
python中的urlencode与urldecode
2019-05-01
windows下python ide关联.py文件
2019-05-01
PHP过滤器函数
2019-05-01
PHP验证过滤器Validate filters
2019-05-01
IP地址分类
2019-05-01
PHP清洗过滤器Sanitize filters
2019-05-01
PHP回调过滤器及回调函数写法
2019-05-01
PHP命名空间简介
2019-05-01
Myeclipse安装testng插件(插件式安装)
2019-05-01
Retrofit
2019-05-01
详细介绍Java和C++区别
2019-05-01
Java数据结构和算法:位运算
2019-05-01
Android进程保活招式大全
2019-05-01
夜间模式的实现套路
2019-05-01
软件设计之高内聚低耦合
2019-05-01
Android学习之路
2019-05-01