贪心算法

贪心算法（Greedy Algorithms）是一类重要的算法设计范式，属于组合优化问题的求解方法。贪心算法的核心思想是在算法的每一步决策中，都做出在当前状态下看起来最优的选择，而不考虑该选择对未来决策可能产生的影响。算法期望通过一系列局部最优选择，最终达到全局最优解。

从算法设计的角度来看，贪心算法与动态规划算法形成了本质上的区别。动态规划算法在做出决策之前，需要先求解所有相关的子问题，然后基于这些子问题的解来做出当前的最优决策，这是一个自底向上的、需要全局信息的决策过程。而贪心算法则采用自顶向下的策略，在子问题被求解之前就做出选择，该选择仅依赖于当前状态，不依赖于任何未来子问题的解。一旦做出选择，算法便不再回溯或修改该选择。

贪心算法的优势在于，当一个问题确实适合使用贪心策略求解时，其算法实现通常比动态规划更简洁，时间复杂度也更低。然而，贪心算法的正确性并非显而易见。对于给定的优化问题，如何确定一个看似短视的贪心策略能够保证得到全局最优解，这需要严格的数学证明。许多看似适合贪心策略的问题实际上存在陷阱，局部最优选择可能导致全局次优解。

因此，学习贪心算法的关键不仅在于掌握算法实现，更在于理解如何严格证明贪心策略的正确性。这需要深入理解问题的数学结构，识别问题的关键性质，并运用形式化的证明方法。

贪心算法的理论基础

一个优化问题能够使用贪心算法求解，需要满足两个关键性质：贪心选择性质（Greedy-Choice Property）和最优子结构（Optimal Substructure）。这两个性质共同保证了局部最优选择的正确性和有效性。

贪心选择性质 (Greedy-Choice Property)

贪心选择性质是贪心算法与动态规划算法最核心的区别。该性质表明，我们可以通过做出一个局部的、贪心的选择来直接构造全局最优解的一部分。形式化地表述为：对于问题的任意实例，总存在一个全局最优解包含我们所做的第一个贪心选择。

在动态规划中，每一步的决策都依赖于所有相关子问题的解，决策是在子问题求解之后做出的。而在贪心算法中，决策是在子问题被求解之前就做出的，我们直接断定该选择是通往最优解的正确一步，然后才去求解由该选择产生的、规模更小的子问题。

证明贪心选择性质是设计贪心算法时最关键也最困难的一步。标准的证明方法称为交换论证法（Exchange Argument），其证明框架如下：

设 $S$ 是问题的一个最优解，$g$ 是我们的贪心选择。如果 $g \in S$，则性质得证。如果 $g \notin S$，我们需要证明存在一个最优解 $S'$，使得 $g \in S'$ 且 $|S'| = |S|$（对于最大化问题）或目标函数值 $f(S') \leq f(S)$（对于最小化问题）。通常的做法是构造一个新解 $S' = (S \setminus \{x\}) \cup \{g\}$，其中 $x$ 是 $S$ 中的某个元素，然后证明 $S'$ 仍然是可行解且不劣于 $S$。

通过交换论证法，我们证明了总是可以安全地做出贪心选择，因为总存在一个最优解包含该选择。

最优子结构 (Optimal Substructure)

最优子结构性质与动态规划中的定义相同，指的是问题的最优解包含其子问题的最优解。对于贪心算法而言，这意味着在做出贪心选择后，原问题被简化为一个规模更小的、类似的子问题。我们只需要求解该子问题的最优解，然后将其与已做出的贪心选择合并，即可得到原问题的最优解。

形式化地表述为：设原问题为 $P$，贪心选择为 $g$，选择 $g$ 后产生的子问题为 $P'$。如果 $S$ 是 $P$ 的包含 $$ 的最优解，那么 必须是子问题 的最优解。

例如，在最短路径问题中，如果我们贪心地选择第一步到达顶点 $v$，且最优子结构性质成立，那么从起点到终点的最短路径必然包含从 $v$ 到终点的最短路径。

贪心算法与动态规划的比较

贪心算法和动态规划都要求问题具有最优子结构性质，但它们在决策方式上存在根本差异。动态规划在做出决策前需要考察所有相关子问题的解，而贪心算法则基于当前状态直接做出决策。动态规划通常采用自底向上的方法，计算并存储所有子问题的解；贪心算法则采用自顶向下的方法，一路做出贪心选择且不可反悔。动态规划的核心在于识别重叠子问题并避免重复计算，而贪心算法的核心在于证明贪心选择性质。

当一个问题同时满足贪心选择性质和最优子结构性质时，我们就可以设计一个高效的贪心算法来解决它。在接下来的案例研究中，我们将通过具体例子来实践如何识别和证明这两个性质。

案例研究：活动选择问题

活动选择问题（Activity Selection Problem）是贪心算法的经典范例。该问题结构清晰，能够很好地展示贪心策略的设计和证明过程，同时深刻揭示贪心思想的本质。

上述问题定义

设 $S = \{a_1, a_2, \ldots, a_n\}$ 是 $$ 个需要使用同一公共资源（如教室、会议室或机器）的活动集合。每个活动 有一个开始时间 和一个结束时间 ，满足 。活动 的时间区间为 ，即左闭右开区间。如果两个活动 和 的时间区间不重叠，即 ，则称它们是兼容的（compatible）。

问题的目标是：从集合 $S$ 中选出一个由相互兼容的活动组成的、规模最大的子集。

考虑以下活动集合实例：

该实例的一个最优解为 $\{a_1, a_4, a_8, a_{11}\}$，包含 4 个活动。另一个最优解为 。

贪心策略的探索

在确定正确的贪心策略之前，我们先考察几种看似合理的直觉策略，分析它们失败的原因，这有助于我们理解问题的本质难点。

策略一：选择开始时间最早的活动。 该策略总是选择当前所有未安排活动中开始时间最早的那个。反例：考虑活动集合 $\{[1, 10), [2, 3), [4, 5)\}$。该策略会首先选择 $[1, 10)$，因为它开始最早。但一旦选择了它，其他两个活动都无法被选择。而最优解是选择 $\{[2, 3), [4, 5)\}$，包含两个活动。因此该策略失败。

策略二：选择持续时间最短的活动。 该策略总是选择持续时间 $f_i - s_i$ 最短的活动。反例：考虑活动集合 $\{[1, 4), [5, 8), [3, 6)\}$。最短的活动是 。但一旦选择了它， 和 都无法被选择。而最优解是选择 。因此该策略也失败。

策略三：选择与其他活动重叠最少的活动。 该策略预先计算每个活动与其他活动的重叠数量，然后选择重叠数最少的。该策略不仅计算复杂度高，而且同样不能保证最优性。

正确的贪心策略

正确的贪心策略是：总是选择结束时间最早的活动。

该策略的直觉是：选择一个尽早结束的活动，可以使得公共资源尽快被释放，从而为后续尽可能多的活动提供安排机会。

算法的执行步骤如下：首先，将所有活动按照结束时间 $f_i$ 从小到大排序。然后，选择第一个活动（即结束时间最早的那个）加入解集。接着，从剩余活动中剔除所有与已选择活动不兼容的活动。最后，在余下的兼容活动中重复上述选择过程，直到没有活动可选。

贪心策略的正确性证明

现在我们运用理论框架，严格证明该策略的正确性。

贪心选择性质的证明

我们需要证明：选择结束时间最早的活动这一贪心选择，总能导向一个最优解。

证明（交换论证法）：

设 $S = \{a_1, a_2, \ldots, a_n\}$ 是按结束时间排好序的活动集合，即 $$。因此 是结束时间最早的活动，我们的贪心选择就是 。

设 $A \subseteq S$ 是问题的一个最优解。我们需要证明，总存在一个最优解包含 $a_1$。

设 $a_j$ 是 $A$ 中结束时间最早的活动，即对所有 $a_k \in A$，有 $f_j \leq f_k$。

情况一： 如果 $a_j = a_1$，那么最优解 $A$ 已经包含了我们的贪心选择 $a_1$。证明完毕。

情况二： 如果 $a_j \neq a_1$，这意味着最优解 $A$ 没有选择 $a_1$。由于 是所有活动中结束时间最早的，我们有 。

现在，我们构造一个新解 $A' = (A \setminus \{a_j\}) \cup \{a_1\}$。即从最优解 中去掉结束时间最早的活动 ，然后加入我们的贪心选择 。

我们来验证 $A'$ 的性质：

兼容性： 在原最优解 $A$ 中，由于 $a_j$ 是 $A$ 中结束时间最早的活动，$A$ 中其他所有活动的开始时间都必须满足 $s_k \geq f_j$（其中 ）。由于 ，我们有 。因此，将 替换为 后， 与 中除 外的其他所有活动都是兼容的。所以 是一个兼容的活动集合。

规模： $|A'| = |A|$，$A'$ 的规模与原最优解相同。

因此，$A'$ 也是一个最优解，且包含了我们的贪心选择 $a_1$。

这就证明了，总存在一个最优解以贪心选择 $a_1$ 开始。贪心选择性质成立。

最优子结构的证明

在做出贪心选择 $a_1$ 之后，原问题被简化为：从所有与 $a_1$ 兼容的活动中，选出最大数量的兼容活动。

设 $S' = \{a_i \in S \mid s_i \geq f_1\}$ 为所有在 结束后才开始的活动的集合。子问题是：为 找出一个最大兼容活动子集。

证明：

设 $A$ 是原问题的一个包含 $a_1$ 的最优解。那么 $A' = A \setminus \{a_1\}$ 是子问题 的一个解。我们需要证明 是子问题 的最优解。

使用反证法：假设 $A'$ 不是 $S'$ 的最优解。那么存在 $S'$ 的一个解 $B'$，使得 。

我们可以构造原问题的一个新解 $B = B' \cup \{a_1\}$。由于 $B'$ 中所有活动都与 $$ 兼容（因为 ，而 中的活动都满足 ），所以 是一个兼容的活动集合。

其规模为 $|B| = |B'| + 1 > |A'| + 1 = |A|$。

这与 $A$ 是原问题的最优解相矛盾。因此，假设不成立，$A'$ 必须是子问题 $S'$ 的最优解。

最优子结构性质成立。

算法实现

基于以上证明，我们可以给出贪心算法的实现。算法的输入是两个数组 $s[1..n]$ 和 $f[1..n]$，分别表示 $n$ 个活动的开始时间和结束时间。输出是一个最大兼容活动子集。

|
GREEDY-ACTIVITY-SELECTOR(s, f, n)
  // 输入：s[1..n] 和 f[1..n] 分别表示 n 个活动的开始时间和结束时间
  //      假设活动已按结束时间 f[1] ≤ f[2] ≤ ... ≤ f[n] 排序
  // 输出：最大兼容活动子集 A
  
  A = {a_1}  // 选择第一个活动
  k = 1      // k 记录最近选择的活动索引
  
  for i = 2 to n
      if s[i] ≥ f[k]  

复杂度分析：

如果活动已经按结束时间排好序，算法只需要一次线性扫描，时间复杂度为 $O(n)$。如果需要先排序，则总的时间复杂度由排序主导，为 $O(n \log n)$。空间复杂度为 $O(1)$（不包括输出数组）。

与动态规划解法相比（通常时间复杂度为 $O(n^2)$），贪心算法在时间复杂度上具有明显优势。

活动选择问题演示

案例研究：霍夫曼编码

霍夫曼编码（Huffman Coding）是贪心算法在数据压缩领域的经典应用。该算法由 David A. Huffman 于 1951 年提出，用于生成最优前缀码，能够显著减少数据存储或传输所需的空间。

前缀码基础

在数据编码中，我们可以用二进制串来表示不同的字符。编码方式主要分为两类：定长编码（Fixed-length Code）和变长编码（Variable-length Code）。

定长编码中，每个字符都用相同长度的二进制串表示。例如，ASCII 码就是一种定长编码，每个字符用 8 位表示。定长编码的优点是实现简单，解码直接，但缺点是无法利用字符出现频率的差异来优化编码长度。

变长编码允许不同字符使用不同长度的二进制串。其核心思想是：为出现频率高的字符分配较短的编码，为出现频率低的字符分配较长的编码，从而在整体上减少编码所需的总位数。然而，变长编码可能带来解码的歧义性。例如，如果字符 'a' 编码为 '0'，字符 'b' 编码为 '01'，那么二进制串 '01' 既可以解码为 'ab'，也可以解码为 'b'，存在歧义。

为了解决解码歧义问题，我们引入前缀码（Prefix Code）的概念。前缀码的定义是：任何字符的编码都不是另一个字符编码的前缀。例如，编码表 $\{'a': '0', 'b': '10', 'c': '110'\}$ 就是一个前缀码。解码器在读取 时，就知道它唯一对应 ，而不可能是更长编码的开始。

前缀码可以被优雅地表示为一棵二叉树，其中所有字符都位于叶子节点。从根到某个字符叶子节点的路径定义了该字符的编码：左分支代表 '0'，右分支代表 '1'。这种表示方法保证了前缀码的性质：由于所有字符都在叶子节点，从根到任意字符的路径不可能是另一条路径的前缀。

问题定义

给定一个字符集 $C$ 以及每个字符 $c \in C$ 的出现频率 $f(c)$，我们的目标是找到一个最优的前缀码，使得编码一个包含这些字符的文件所需的总位数最少。

设 $T$ 是一棵编码树，$d_T(c)$ 是字符 $c$ 在树 $T$ 中的深度（即其编码长度）。编码文件所需的总位数 $B(T)$ 等于所有字符的频率与其编码长度的乘积之和，即对每个字符 $$，计算 并求和。

我们的目标是找到一棵编码树 $T^*$，使得 $B(T^*) = \min_T B(T)$。

霍夫曼算法的贪心策略

霍夫曼算法采用自底向上构建编码树的策略，其核心思想是：在每一步都将当前具有最低频率的两个节点合并。

算法的直觉是：频率最低的两个字符理应在编码树的最深处，拥有最长的码长。将它们合并，可以看作是将它们从待处理的字符集中移除，并用一个代表它们合并的新虚拟字符来替代，该虚拟字符的频率是两者之和。这个过程不断重复，频率较高的字符或字符组会较晚被合并，因此它们会处于树的较浅位置，获得较短的码长。

算法使用一个最小优先队列（Min-Priority Queue，通常用最小堆实现）来维护节点，队列根据节点的频率进行排序。

|
HUFFMAN(C)
  // 输入：字符集 C，每个字符 c 有频率 f(c)
  // 输出：霍夫曼编码树的根节点
  
  n = |C|
  
  // 初始化最小优先队列 Q，包含所有字符节点
  Q = BUILD-MIN-HEAP(C)  // 根据频率 f(c) 构建最小堆
  
  // 循环 n-1 次，构建树
  for i = 1 to n - 1
      // 分配一个新内部节点 z
      z = 

复杂度分析：

算法需要执行 $n-1$ 次合并操作。每次操作包括两次 EXTRACT-MIN 和一次 INSERT，这些操作在最小堆上的时间复杂度都是 $O(\log n)$。因此，算法的总时间复杂度为 $O(n \log n)$。空间复杂度为 $O(n)$，用于存储树节点和优先队列。

算法示例

考虑以下字符和频率：$f:5, e:9, c:12, b:13, d:16, a:45$。

算法的执行过程如下表所示：

最终的霍夫曼树结构如下：

从树中可以读出每个字符的编码：$a: 0$，$c: 100$，$b: 101$，$d: 111$，$f: 1100$，。

正确性证明

霍夫曼算法的正确性可以通过证明其满足贪心选择性质和最优子结构来确立。

贪心选择性质的证明概要：

设 $x$ 和 $y$ 是频率最低的两个字符，即 $f(x) \leq f(y) \leq f(c)$ 对所有 $c \in C \setminus \{x, y\}$ 成立。我们需要证明：总存在一个最优编码树，其中 和 是兄弟节点（即有共同的父节点），并且它们位于树的最深层。

证明思路（交换论证法）：假设存在一个最优编码树 $T$，但 $x$ 和 $y$ 在其中不是兄弟。设 $b$ 和 $c$ 是一对在最深层的兄弟叶子节点。我们可以通过交换操作，将 $x$ 与 $b$ 交换位置，$y$ 与 交换位置，得到一棵新树 。可以证明，新树 的总编码成本不会高于原树 ，因此 也是最优的。而在 中， 和 成为了最深层的兄弟。这证明了将 和 首先合并的贪心选择是安全的。

最优子结构的证明概要：

如果我们将 $x$ 和 $y$ 合并成一个虚拟父节点 $z$，其频率为 $f(z) = f(x) + f(y)$，并为新的、规模减一的字符集 $C^{\mathrm{\prime }}$ 找到一个最优编码树 ，那么，将 中代表 的叶子节点替换为包含 和 作为孩子的内部节点，所得到的新树 对于原始字符集 来说，也是最优的。

这个性质保证了我们可以通过递归地解决子问题来构建全局最优解。

由于同时满足这两个性质，霍夫曼算法的正确性得证。

其他贪心算法应用

贪心算法作为一种基本的设计范式，在算法设计中具有重要地位。许多图论中的经典算法都体现了贪心思想。

迪杰斯特拉算法（Dijkstra's Algorithm） 用于计算图中单源最短路径，其核心是一种贪心策略：维护一个已找到最短路径的顶点集合 $S$，每次都贪心地从 $S$ 外部选择一个距离 $S$ 最近的顶点加入集合。该算法要求图中所有边的权重非负。

最小生成树算法 用于寻找图的最小生成树（Minimum Spanning Tree），其中两种经典算法都基于贪心策略：

克鲁斯卡尔算法（Kruskal's Algorithm） 将所有边按权重排序，每次都贪心地选择权重最小且不会形成环的边加入到生成树中。该算法使用并查集（Union-Find）数据结构来高效地检测环。

普里姆算法（Prim's Algorithm） 从一个顶点开始，每次都贪心地选择连接已选顶点和未选顶点的、权重最小的边。该算法可以使用优先队列来高效实现。

这些算法的成功都依赖于其背后的问题结构满足贪心选择性质和最优子结构。例如，对于最小生成树问题，可以证明"总有一棵最小生成树包含图中权重最小的那条安全边"，这就是贪心选择性质的体现。

因此，当面对一个新的优化问题时，算法设计师需要首先判断该问题是否适合使用贪心策略。如果答案是肯定的，通常意味着一个更简单、更高效的解决方案。然而，这个判断必须建立在严谨的数学证明之上，否则贪心策略可能导向错误的结果。

练习题

问题一：分发糖果

有 $N$ 个孩子站成一条直线，老师根据每个孩子的表现给出评分数组 ratings。需要按照以下规则分发糖果：每个孩子至少分配到 1 个糖果；相邻的孩子中，评分高的孩子必须获得更多的糖果。求最少需要准备多少个糖果。

|
输入：ratings = [1, 0, 2]
输出：5
解释：可以分别给第一个、第二个、第三个孩子分发 2、1、2 个糖果。

问题二：跳跃游戏

给定一个非负整数数组 nums，初始位于数组的第一个位置。数组中的每个元素代表在该位置可以跳跃的最大长度。判断是否能够到达最后一个位置。

|
输入：nums = [2, 3, 1, 1, 4]
输出：true
解释：可以先跳 1 步，从位置 0 到达位置 1，然后再从位置 1 跳 3 步到达最后一个位置。

问题三：加油站

在一条环路上有 $N$ 个加油站，其中第 $i$ 个加油站有汽油 gas[i] 升。从第 $i$ 个加油站开往第 $i+1$ 个加油站需要消耗汽油 cost[i] 升。从某个加油站出发，开始时油箱为空。如果可以绕环路行驶一周，返回出发时加油站的编号，否则返回 $-1$。

|
输入：gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
输出：3
解释：从 3 号加油站（索引为 3）出发，可以获得 4 升汽油。此时油箱有 0 + 4 = 4 升汽油。
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油。
开往 0 号加油站，此时油箱有 8 -

问题四：任务调度

给定一个用字符数组表示的任务列表，包含使用大写字母 A-Z 表示的 26 种不同种类的任务。任务可以以任意顺序执行，每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内可以执行一个任务，或者在待命状态。两个相同种类的任务之间必须有长度为 $n$ 的冷却时间，因此至少有连续 $n$ 个单位时间内 CPU 在执行不同的任务，或者在待命状态。计算完成所有任务所需要的最少时间。

|
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

问题五：买卖股票的最佳时机 II

给定一个数组 prices，其中 prices[i] 是股票第 $i$ 天的价格。设计一个算法来计算所能获取的最大利润。可以完成多次交易（多次买卖一支股票），但不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。

|
输入：prices = [7, 1, 5, 3, 6, 4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 3 = 3。
总利润为 4 + 3