问题 AA: 算法设计与分析 一般背包问题
2021/5/8 1:25:52
本文主要是介绍问题 AA: 算法设计与分析 一般背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为W,的物品。岛上金属有s个种类, 每种金属重量不同,分别为n1,n2,n3 … ns,同时每个种类的金属总的价值也不同,分别为v1,v2, …vs。KID想一次带走价值尽可能多的金属,
问他最多能带走价值多少的金属。注意到金属是可以被任意分割的,并且金属的价值和其重量成正比。
输入
第1行是测试数据的组数k,后面跟着k组输入。
每组测试数据占3行,第1行是一个正整数w(1<=w<=10000),表示口袋承重上限。第2行是一个正整数s (1 <= s <=100),表示金属种类。第3行有2s个正整数,分别为n1, v1, n2, v2, … , ns, vs分别为第一种,第二种,…,第s种金属的总重量和总价值(1<=ni<= 10000, 1<=vi<=10000)。
输出
k行,每行输出对应一个输入。输出应精确到小数点后2位。
样例输入 Copy
2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43
样例输出 Copy
171.93
508.00
#include <bits/stdc++.h> using namespace std; const int N = 100; struct Node { int w, v; double avg; } a[N]; bool cmp(Node a, Node b) { return a.avg > b.avg; } int main() { int k, w, s; scanf("%d", &k); while (k--) { scanf("%d%d", &w, &s); for (int i = 0; i < s; i++) { scanf("%d%d", &a[i].w, &a[i].v); a[i].avg = (double)a[i].v / (double)a[i].w; } sort(a, a + s, cmp); double tot = 0; for (int i = 0; i < s; i++) if (w >= a[i].w) { w -= a[i].w; tot += a[i].v; } else { tot += w * a[i].avg; break; } printf("%.2f\n", tot); } return 0; }
这篇关于问题 AA: 算法设计与分析 一般背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)