贪心算法
贪心算法，也称为贪心法，是指在求解问题时采用贪心策略，通过每一步选择中的最优解，来达到全局最优解的算法。它是一种在某些情况下可以得到正确答案的算法，而且算法复杂度通常较低，因此被广泛应用。
作用
贪心算法的作用非常广泛，可以应用于以下问题和场景中：
- 资源分配问题
- 最小生成树问题
- 最短路径问题
- 集合覆盖问题
- 背包问题
- 排序问题
- … …
贪心算法最重要的特点是其高效性，通常在问题可解时能够得到全局最优解，而且往往不需要进行大量的计算。同时，贪心算法相对于其他优化算法如动态规划、回溯等，更容易理解和实现。
使用方法
贪心算法使用的过程通常可以分为以下三个步骤：
- 特性分析：通过对问题的思考，确定其具有的贪心策略和适用条件。
- 设计贪心策略：基于问题特性，设计出贪心策略。
- 证明最优性：通过针对问题和策略的分析，证明所得策略的正确性和最优性。
下面，我们将通过两个实例来说明贪心算法的用法。
示例一：零钱兑换
问题描述：假设现在有5元钱要用不同面额的硬币兑换成1分、5分、10分、50分、1元的硬币，问最少需要多少个硬币才能兑换完成？
根据这道题目的特性分析，我们可以知道这是一道典型的贪心算法问题。因为在兑换的过程中，每次都应该优先选择面额最大的硬币，因为这样最后得到的硬币数量才会更少。
基于这样的特性，我们可以设计出贪心策略如下：
- 尽量选用面额大的硬币。
- 尽量让所有的硬币数量最小。
根据贪心策略，我们可以首先选择面额为1元的硬币，得到1张5元的硬币和0张其他硬币。接着，我们选择面额为5分的硬币，得到1张5元的硬币和5张5分的硬币。然后依次选择10分、50分、1元的硬币，得到结果为1张5元、1张1元、1张50分、1张10分、5张5分，共计9张硬币。
由于该贪心策略满足问题的特定性质，因此我们可以得到正确答案。
示例二：区间选点
问题描述：现在有 n 个区间，每个区间的两端分别标记为左端点和右端点，现在要求在每个区间内选择恰好一个点，使得每个区间内的点能够覆盖该区间，而且所选点的数量要尽量少。问选择的点的最小数量是多少？
同样地，我们可以通过特定性分析，发现这也是一道贪心算法问题。由于相邻的区间之间可能会有重叠的部分，因此我们应该优先选择右端点较小的区间，这样可以保证选择的点数量最小。
基于这样的特性，我们可以设计出贪心策略如下：
- 尽量选用右端点较小的区间。
根据该贪心策略，我们可以先将n个区间按照右端点的大小进行排序。选择右端点最小的第一个区间，并将其右端点作为候选点。接着，我们依次遍历每个区间，如果该区间的左端点大于候选点，则将该区间的右端点置为候选点。最终，我们得到的候选点的数量即为所选点的最小数量。
贪心策略满足问题的特性，因此我们可以得到正确答案。
总结
贪心算法在很多情况下可以得到正确的答案，并且算法复杂度通常较低。但值得注意的是，贪心算法并不能适用于所有问题。因此，我们在使用贪心算法时，需要深入理解问题特性，合理设计贪心策略，并通过证明最优性来确保策略的正确性。