【普及】贪心算法专项训练

Update Log

贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择，因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。

从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。

当接下来的任意一步都无法达到最优时，贪心算法结束。

下面给出一些例题。

电池的寿命

有很多电池，使用寿命有所不同，需要两个电池。譬如有的能使用 5 个小时，有的可能就只能使用 3 个小时，此时只能用 3 个小时，有一个电池剩下的电量无法使用，因为我们需要 2 枚电池同时使用。现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。

那么我们来分析一下两种情况。

综上所述：

这样只需要 O(n) 的输入后就可以得出答案，仅需判断并求和即可，没有难度

【深基12.例1】部分背包问题

这道题也是一个很简单的贪心。其实此题所谓的背包问题，看似需要使用动态规划，但是，所有金币都可以随意分割，那么显而易见的方法是：

货币使用问题

尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。

区间调度问题

工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。

迪杰斯特拉算法也是基于贪心的一种算法，其基本原理：

注：可以用堆或者优先队列进行优化。

训练贪心算法，可以从以下的几个方面：

本次的题库依然按照难度排序，面向普及，按难度排序，适合由浅入深的同学，难度不超过紫，也会有橙题等适合入门的题目，可以循序渐进。