贪心 单选贪心
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了贪心 单选贪心,现在分享给大家,供学习和参考。文章包含948字,纯文字阅读大概需要3分钟。
教程信息
单选类贪心:以部分背包问题为例
单选类贪心指的是,从多个选项中,每次贪心选择出一个当前规模下的最优解,
典型的问题是部分背包问题。
通过题目解题认识单选贪心
题目来源:
https://www.luogu.com.cn/problem/P2240
题目内容:
【P2240 部分背包问题】
部分背包问题使用的贪心策略是:“从单价高的开始装,装到不能装为止”。
贪心策略的正确性可以通过反证法进行证明:
所有的东西价值都是正的,因此只要金币总数足够,背包就必须要装满而不能留空;假设没在背包中放入单价高的金币,而放入了单价低的金币,那么可用等重量的高价值金币替换掉背包里的低价值金币,总价值更高了。
实现代码:
#include<bits/stdc++.h> using namespace std; struct mo { int m, v; }; bool cmp(mo mo1, mo mo2) { return mo1.v * mo2.m > mo2.v * mo1.m; //浮点数有误差,最好不要写成mo1.v/mo1.m>mo2.v/mo2.m } int main() { int n, t; cin >> n >> t; mo a[n]; for (int i = 0; i < n; i++) cin >> a[i].m >> a[i].v; sort(a, a + n, cmp); double sum = 0; for (int i = 0; i < n; i++) if (t >= a[i].m) { sum += a[i].v; t -= a[i].m; } else { sum += (a[i].v * 1.0 / a[i].m) * t; break; } cout << fixed << setprecision(2) << sum; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供贪心 单选贪心的全部内容,希望教程文章能够帮你了解学习贪心 单选贪心,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-331.html