贪心类问题
标签: 机试攻略 - 高分篇
学习人数: 24.7k


高清播放
赞赏支持

贪心类问题是很常见的考点,贪心算法更重要的是一种贪心的思想,它追求的是当前最优解,从而得到全局最优解。贪心类问题基本上算是必考题型之一,它能更好的考察出学生的思维能力以及对问题的分析能力,很多学校的出题人都非常爱出贪心类的题目。

 

贪心算法的定义:

贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

 

贪心可以很简单,简单到让所有人一眼就能看出来该怎么做。贪心也可以很难,难到让你没办法去证明这样贪心的正确性。所以要想解决贪心这类问题,主要还是看你的悟性,看你对题目的分析能力如何,下面我们举例说明。

例子1:地上有3张纸币,分别是5元、1元和10元,问你只能拿一张,最多能拿多少钱?
解析:很明显,10元。
例子2:地上有n张纸币,有1元的,有5元的,还要10元的,问你只能拿一张,最多能拿多少钱?
解析:很明显,还是10元。
例子3:地上有很多纸币,有a张1元的,有b张5元的,还要c张10元的,问你从中拿x张,最多能拿多少钱?
解析:大家应该都能想到,肯定是优先拿10元的,如果10元的拿完了,再拿5元的,最后才会拿1元的。这就是贪心的思想,所以贪心其实是很容易想到的。
例子4:有n个整数构成的集合,现在从中拿出x个数来,问他们的和最大能是多少?
解析:相信大家都能想到,优先拿大的,从大到小一个个拿,这样组成的和最大。那么在解决这个问题之前,我们需要先排序,从大到小的排好序,然后将前x个数的和累加起来就是答案。

从上面几个例子中,相信大家对贪心已经有了初步的了解。我们使用贪心的时候,往往需要先按照某个特性先排好序,也就是说贪心一般和sort一起使用。

 

喝饮料
题目描述:
商店里有n中饮料,第i种饮料有mi毫升,价格为wi。
小明现在手里有x元,他想吃尽量多的饮料,于是向你寻求帮助,怎么样买才能吃的最多。
请注意,每一种饮料都可以只买一部分。
输入描述:
有多组测试数据。
第一行输入两个非负整数x和n。
接下来n行,每行输入两个整数,分别为mi和wi。
所有数据都不大于1000。
x和n都为-1时程序结束。
输出描述:
请输出小明最多能喝到多少毫升的饮料,结果保留三位小数。
输入样例#:
233 6 
6 1
23 66
32 23
66 66
1 5
8 5
-1 -1
输出样例#:
136.000
题目来源:
DreamJudge 1478

题目解析:通过分析之后我们可以发现,小明想要喝尽量多的饮料的话,肯定优先选择性价比最高的饮料喝,也就是说1毫升的价格最低的饮料先喝,那么我们就需要去比较,每种饮料1毫升的价格是多少。然后按照这个单价从低到高依次排序,然后一个一个往后喝,这样可以保证小明能喝到最多的饮料。

 

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
struct node {  
    double w, m;  
}p[1005];  
bool cmp(node a, node b) ...
登录查看完整内容


课后作业

练习题目

DreamJudge 1307 组队刷题
DreamJudge 1347 To Fill or Not to Fill


登录后开始许愿

暂无评论,来抢沙发