登录以参加训练计划

贪心原理

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

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

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

贪心算法的弊病

不能保证求得的最后解是最佳的； 不能用来求最大或最小解问题； 只能求满足某些约束条件的可行解的范围。 下面给出一些例题。

电池的寿命

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

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

如果有一枚电池，电量比任何其他的电池之和都要大，很容易得到把其他电池用完就是最优解了。 如果不存在这枚电池，性感理解一下，就是把最大的电池拿出来，将其他的电池一点一点消耗到和这枚电池一样，然后全部用掉。 综上所述：

若存在大于总电量一半的电池，输出其余电池的总电量。 反之输出全部的电量。 这样只需要 O(n)O(n) 的输入后就可以得出答案，仅需判断并求和即可，没有难度

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

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

性价比排列，从最高性价比一直往下拿，拿到拿不动或者拿光了为止，是不是很简单？ 核心思想：能拿就全拿，拿不下能拿多少拿多少，贵的先拿。

货币使用问题

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

区间调度问题

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

Dijkstra & Prim

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

循环找到当前离当前节点最近的节点（贪心）。 注：可以用堆或者优先队列进行优化。

向下走，如果比之前标记过的最短路更短，就将这个节点进行标记（松弛）。 将整个图走一遍，无优化时间复杂度 O(n^2)。 每次都找最优，所以有局限，不能应对有负边的图。

题目选择

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

尝试着证明一道题贪心的正确性。 对于一道动规题目尝试举出贪心的反例。 尝试优化贪心，反悔贪心。 本次的题库依然按照难度排序，面向普及，按难度排序，适合由浅入深的同学，难度不超过紫，也会有橙题等适合入门的题目，可以循序渐进。