一文带你“看透”贪心算法：概念、代码与应用

文章摘要：贪心算法是一种通过局部最优选择寻求全局最优解的算法策略，具有简单高效的特点，但并非适用于所有问题。文章系统介绍了贪心算法的概念、特点、应用场景和代码实现，并通过找零钱和活动选择等经典案例进行说明。重点分析了贪心算法与动态规划、分治法的区别，以及判断问题是否适用贪心算法的三个关键标准：贪心选择性质、最优子结构性质和反证法验证。文章指出贪心算法在满足特定条件的问题中表现优异，但也存在局限性

大雨淅淅1999

579人浏览 · 2025-08-25 22:58:10

大雨淅淅1999 · 2025-08-25 22:58:10 发布

一、贪心算法：到底是什么？

为了让大家更好地理解贪心算法，先给大家举个生活中的例子。假设你去超市购物，结账时收银员需要找给你一定金额的零钱。现在有 100 元、50 元、20 元、10 元、5 元、1 元这些面额的纸币和硬币，收银员为了让找零的纸币和硬币数量最少，会优先选择大面额的货币。比如要找 63 元，他会先给你一张 50 元，再给一张 10 元，然后给一张 2 元，最后给一张 1 元，而不是先给你 63 张 1 元。这种每次都选择当前最优（最大面额）的策略，就是贪心算法的基本思想。

贪心算法（Greedy Algorithm），又称贪婪算法，在对问题求解时，总是做出在当前看来是最好的选择，也就是只考虑眼前的最优解，不从整体最优上加以考虑，所做出的选择只是在某种意义上的局部最优解。贪心算法每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，在一些最优解问题的求解上表现得更简单、更迅速。但它不是对所有问题都能得到整体最优解，关键在于贪心策略的选择。

二、贪心算法的特点

贪心算法作为一种常用的算法策略，具有独特的特点，这些特点决定了它在不同场景下的适用性和效率。接下来，我们就来详细分析一下贪心算法的优点与缺点。

2.1 优点

简单易实现：贪心算法在每一步决策时，只需要考虑当前的最优选择，不需要对未来的状态进行预测和复杂的计算。以找零问题为例，我们在代码实现时，只需要按照面额从大到小的顺序依次选择硬币，每一次选择都是当前情况下能使找零硬币数量最少的选择，代码实现逻辑简单明了。这样的实现方式，相较于一些需要复杂递归或动态规划的算法，大大降低了编程的难度和代码的复杂度。

时间复杂度低：在很多情况下，贪心算法的时间复杂度相对较低。比如在不考虑排序的前提下，对于一些简单的贪心问题，其时间复杂度可以达到 O (n) 。这是因为贪心算法每次只对当前情况进行一次计算和选择，不需要进行大量的重复计算或对所有可能情况进行遍历。以活动选择问题为例，假设我们有 n 个活动，每个活动都有开始时间和结束时间，我们只需要对活动按照结束时间进行一次排序（假设排序时间复杂度为 O (nlogn)），然后依次遍历活动，每次选择结束时间最早且与已选活动不冲突的活动，这个遍历过程的时间复杂度为 O (n)。所以，整个算法的时间复杂度主要取决于排序的时间复杂度 O (nlogn)，在数据规模较大时，这种低时间复杂度的优势就会更加明显，能够快速地得到问题的解。

2.2 缺点

不能保证得到最优解：贪心算法的每一步选择都是基于当前状态的最优决策，而不考虑这个选择对未来的影响。这就导致在某些情况下，局部最优解的组合并不能得到全局最优解。比如在 0 - 1 背包问题中，假设背包的容量为 5，有三个物品，物品 1 重量为 2，价值为 3；物品 2 重量为 3，价值为 4；物品 3 重量为 1，价值为 2。如果按照贪心算法，先选择单位重量价值最高的物品，即物品 1（单位重量价值为 3/2 = 1.5），然后再选择物品 3（单位重量价值为 2/1 = 2），此时背包剩余容量为 2，无法再放入物品 2，总价值为 3 + 2 = 5。但实际上，最优解是选择物品 2 和物品 3，总价值为 4 + 2 = 6。这就说明贪心算法在这个问题上不能得到最优解。

难以判断适用问题：贪心算法的有效性高度依赖于问题是否具有贪心选择性质和最优子结构性质。然而，判断一个问题是否具备这些性质并不总是容易的，很多时候需要进行深入的分析和证明。对于一些复杂的问题，很难直观地判断贪心算法是否适用，如果盲目使用贪心算法，可能会得到错误的结果。比如在旅行商问题中，虽然看起来每次选择距离当前城市最近的下一个城市是一种贪心策略，但实际上这种策略并不能保证得到最短的旅行路线，因为它没有考虑到整体的路径规划，可能会陷入局部最优，而无法找到全局最优解。所以，在使用贪心算法之前，需要谨慎地分析问题的性质，确定其是否适合使用贪心算法。

三、贪心算法的应用场景

贪心算法在许多领域都有广泛的应用，从经典的计算机科学问题到实际生活中的资源分配和任务调度。下面我们来看看贪心算法在一些常见场景中的应用。

3.1 经典场景

最小生成树（MST，Minimum Spanning Tree）：在一个连通无向图中，最小生成树是一棵包含图中所有顶点，并且边权之和最小的树。常见的 Prim 算法和 Kruskal 算法都是基于贪心策略来实现的。Prim 算法从任意一个顶点开始，每次选择与当前生成树中顶点相连的边中权值最小的边，将其加入生成树，直到包含所有顶点。Kruskal 算法则是将所有边按权值从小到大排序，依次选择权值最小且不构成环的边加入生成树。比如在通信网络建设中，假设有多个城市，要在这些城市之间铺设通信线路，使得所有城市都能连通，并且铺设的总线路长度最短，就可以使用最小生成树算法来解决。

最短路径算法：以 Dijkstra 算法为例，它用于求解带权有向图中某一源点到其他所有顶点的最短路径。Dijkstra 算法的核心思想是从源点开始，维护一个距离源点的最短距离的集合，每次从集合外选择距离源点最近的顶点，将其加入集合，并更新其他顶点到源点的最短距离。这个过程中，每次选择的都是当前距离源点最近的顶点，体现了贪心算法的思想。例如在地图导航中，要计算从当前位置到目的地的最短路线，就可以运用 Dijkstra 算法来找到最优路径。

3.2 其他应用

资源分配：在资源有限的情况下，如何将资源分配给不同的任务或对象，以实现某种目标的最大化或最小化。比如在内存分配中，系统需要将有限的内存空间分配给多个进程，贪心算法可以根据每个进程的需求和优先级，优先分配给需求紧急或优先级高的进程，以提高系统的整体性能。在云计算资源分配中，也可以使用贪心算法，根据用户的任务量和付费情况，合理分配计算资源，以最大化云服务提供商的收益。

任务调度：对于一系列具有不同开始时间、结束时间和权重（如收益、优先级等）的任务，如何安排任务的执行顺序，以达到最大收益或满足特定条件。例如在车间生产调度中，有多个生产任务，每个任务有不同的加工时间和交货期，使用贪心算法可以根据任务的交货期或加工时间等因素，优先安排交货期紧急或加工时间短的任务，以提高生产效率和按时交货率。在操作系统的任务调度中，也可以运用贪心算法，根据任务的优先级和资源需求，合理分配 CPU 时间片，提高系统的响应速度和吞吐量。

四、贪心算法代码实现

4.1 简单示例：找零钱问题

为了让大家更直观地理解贪心算法的实现过程，我们先来看一个简单的找零钱问题。假设你是一名收银员，需要给顾客找零一定金额，你有 1 元、5 元、10 元、20 元、50 元、100 元的纸币，如何用最少的纸币数量完成找零呢？这就是一个典型的可以用贪心算法解决的问题。我们每次都优先选择面额最大的纸币，直到找零金额为 0。

下面是 Python 实现的代码：

def coin_change(coins, amount):

coins.sort(reverse=True) # 将硬币面额从大到小排序

count = 0 # 记录使用的硬币数量

for coin in coins:

while amount >= coin: # 当剩余金额大于等于当前硬币面额时

amount -= coin # 减去当前硬币面额

count += 1 # 硬币数量加1

if amount != 0: # 如果最后还有剩余金额，说明无法找零

return -1

return count

# 测试

coins = [1, 5, 10, 20, 50, 100]

amount = 63

print(coin_change(coins, amount))

代码思路：

首先，对硬币面额列表coins进行从大到小的排序，这样我们在遍历的时候就可以优先选择大面额的硬币。

初始化一个变量count，用于记录找零所需的硬币数量，初始值为 0 。

遍历排序后的硬币面额列表，对于每一个硬币面额coin，使用while循环来判断剩余找零金额amount是否大于等于当前硬币面额coin。如果是，就从amount中减去coin，并将count加 1，表示使用了一枚当前面额的硬币。这个循环会一直执行，直到amount小于coin，确保我们尽可能多地使用当前大面额的硬币。

当遍历完所有硬币面额后，如果amount不为 0，说明无法用给定的硬币面额组合完成找零，返回 - 1；否则，返回count，即所需的最少硬币数量。

4.2 复杂示例：活动选择问题

接下来，我们看一个更复杂一些的例子 —— 活动选择问题。假设有一系列活动，每个活动都有开始时间和结束时间，我们的目标是选择尽可能多的活动，前提是这些活动之间不能冲突（即一个活动结束后，另一个活动才能开始）。这个问题可以用贪心算法来解决，贪心策略是每次选择结束时间最早的活动，因为这样可以为后续的活动留出更多的时间。

下面是 Python 实现的代码：

def activity_selection(activities):

activities.sort(key=lambda x: x[1]) # 按活动结束时间排序

selected = [activities[0]] # 选择第一个活动

for i in range(1, len(activities)):

if activities[i][0] >= selected[-1][1]: # 如果当前活动开始时间不早于上一个选中活动的结束时间

selected.append(activities[i]) # 选择当前活动

return selected

# 测试

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]

print(activity_selection(activities))

代码思路：

首先，使用sort方法对活动列表activities进行排序，排序的依据是每个活动的结束时间。这里使用了匿名函数lambda x: x[1]，表示按照每个活动元组的第二个元素（即结束时间）进行排序。这样，在后续的选择过程中，我们就可以从结束时间最早的活动开始考虑。

初始化一个列表selected，并将第一个活动（即结束时间最早的活动）添加到selected中，作为第一个被选中的活动。这是贪心算法的第一步选择，因为它结束得最早，能为后续活动留出最多的时间。

从第二个活动开始遍历活动列表，对于每个活动，检查它的开始时间是否大于等于selected列表中最后一个活动（即上一个选中活动）的结束时间。如果满足这个条件，说明当前活动与已选中的活动不冲突，可以将其添加到selected列表中。这个条件保证了每次选择的活动都不会与之前选择的活动在时间上冲突。

遍历结束后，selected列表中存储的就是按照贪心算法选择出来的最多不冲突活动集合，返回这个集合。

通过以上两个例子，希望大家对贪心算法的代码实现有了更深入的理解。在实际应用中，需要根据具体问题的特点来选择合适的贪心策略，并进行相应的代码实现。

五、贪心算法与其他算法的区别

5.1 与动态规划对比

在算法的世界里，贪心算法和动态规划常常被放在一起讨论，它们都用于解决优化问题，但在思路和方法上却有着显著的区别。

动态规划（Dynamic Programming），简称 DP，它的核心思路是将一个复杂问题分解为一系列相互重叠的子问题，通过求解子问题并保存它们的解，来避免重复计算，从而得到原问题的最优解。这就好比你要搭建一座高楼，动态规划会先把高楼分解成一个个小模块，然后逐步搭建这些小模块，并且会记录每个小模块的搭建方式，这样在搭建其他部分时，如果用到相同的小模块，就可以直接使用之前的成果，而不需要重新搭建。

以斐波那契数列为例，动态规划会创建一个数组来保存已经计算出的斐波那契数，从最基础的斐波那契数开始，逐步计算并填充数组，最终得到所求的斐波那契数。在这个过程中，每个子问题的解都依赖于之前子问题的解，通过不断地积累和复用这些解，来高效地解决整个问题。

而贪心算法，就像一个目光短浅的决策者，只考虑眼前的最优选择，不考虑这个选择对未来的影响。还是以搭建高楼为例，贪心算法每次只选择当前看起来最好的材料和搭建方式，而不考虑后续的搭建需求和整体的结构稳定性。

在找零钱问题中，如果用动态规划来解决，需要创建一个数组dp，dp[i]表示凑成金额i所需的最少硬币数量。通过对每个金额i，遍历所有硬币面额coins[j]，更新dp[i]为dp[i]和dp[i - coins[j]] + 1中的较小值。这种方法会考虑所有可能的硬币组合，以找到全局最优解。而贪心算法则直接从最大面额的硬币开始尝试，每次选择当前能使用的最大面额硬币，直到凑出目标金额。虽然在某些情况下（如硬币面额为 1、5、10、20、50、100 等常见面额时），贪心算法能得到最优解，但对于一些特殊的硬币面额组合，贪心算法可能无法得到全局最优解。

总结来说，动态规划适用于子问题重叠且需要全局最优解的问题，它通过保存子问题的解来避免重复计算，虽然时间复杂度和空间复杂度可能较高，但能保证得到全局最优解。贪心算法则适用于具有贪心选择性质的问题，即局部最优选择能导致全局最优解的问题，它的优点是简单高效，但缺点是不能保证对所有问题都能得到全局最优解。在实际应用中，需要根据问题的特点来选择合适的算法。

5.2 与分治法对比

分治法（Divide and Conquer），是将一个大问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题，递归地解决这些子问题，然后将子问题的解合并起来，得到原问题的解。这就像把一个大蛋糕切成几块小蛋糕，分别处理每一块小蛋糕，最后再把处理好的小蛋糕组合起来。

归并排序就是分治法的一个典型应用。在归并排序中，首先将一个无序数组不断地分成两个子数组，直到子数组的长度为 1（此时子数组已经是有序的）。然后，将这些有序的子数组合并成一个更大的有序数组，不断重复这个合并过程，最终得到一个完全有序的数组。在这个过程中，每个子问题的解决都是独立的，不需要依赖其他子问题的中间结果。

贪心算法与分治法的主要区别在于，贪心算法在每一步都做出当前状态下的最优选择，并且这个选择一旦做出就不会更改，它不考虑将问题分解成子问题以及子问题之间的合并。例如在活动选择问题中，贪心算法直接按照活动结束时间的先后顺序，依次选择结束时间最早且与已选活动不冲突的活动，而不会像分治法那样将活动选择问题分解成多个子问题，然后再合并子问题的解。

分治法更侧重于问题的分解和合并，适用于那些可以将大问题分解为多个独立子问题的场景，例如排序、查找等问题。而贪心算法则更注重在每一步做出局部最优选择，适用于具有贪心选择性质的优化问题，如最小生成树、哈夫曼编码等问题。理解这两种算法的区别，有助于我们在面对不同的问题时，选择最合适的算法来解决它们。

六、如何判断问题是否适合贪心算法

在使用贪心算法解决问题时，关键是要判断问题是否适合使用贪心算法。这需要我们分析问题是否具有贪心选择性质和最优子结构性质。下面我们就来详细探讨一下如何判断这两个性质。

6.1 贪心选择性质

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。

以活动选择问题为例，我们的贪心策略是每次选择结束时间最早的活动。假设我们有一系列活动S = {a1, a2, ..., an}，每个活动有开始时间start[i]和结束时间end[i] 。我们要证明这个贪心策略是正确的，即按照结束时间最早的顺序选择活动，最终能得到最大数量的不冲突活动集合。

首先，假设存在一个最优解A，它不是按照结束时间最早的顺序选择活动的。那么在A中，一定存在一个活动ai，它的结束时间不是当前所有可选活动中最早的。我们可以找到一个结束时间最早的活动aj，并且aj与A中已选的活动不冲突（因为如果冲突，A就不是最优解了）。将ai替换为aj，得到一个新的解A' 。由于aj的结束时间更早，所以A'中能选择的活动数量不会比A少，即A'也是一个最优解。这就证明了我们可以从一个整体最优解出发，通过替换，使其以贪心选择开始。

然后，对于剩下的活动集合，我们可以用数学归纳法证明，每次选择结束时间最早的活动，都能得到最优解。假设对于规模为k的活动集合，贪心选择能得到最优解。当活动集合规模为k + 1时，我们先选择结束时间最早的活动ak+1，那么剩下的k个活动集合仍然满足贪心选择性质，根据归纳假设，对剩下的活动集合进行贪心选择也能得到最优解。所以，对于规模为k + 1的活动集合，贪心选择也能得到最优解。通过数学归纳法，我们就证明了活动选择问题具有贪心选择性质。

6.2 最优子结构性质

最优子结构性质是指如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。这是问题可用贪心算法（或动态规划法）求解的关键特征。证明问题是否具有最优子结构性质通常可采用数学归纳法。

还是以活动选择问题为例，我们要证明它具有最优子结构性质。假设我们已经选择了活动ak，那么剩下的问题就是在ak结束之后开始的活动中选择最大数量的不冲突活动。设这个子问题的最优解为B，而原问题的最优解为A 。如果A中除了ak之外的活动集合不是B，那么我们可以用B替换A中除ak之外的活动集合，得到一个新的解A' 。由于B是子问题的最优解，所以A'中活动的数量不会比A少，即A'也是一个最优解。这就说明原问题的最优解包含了子问题的最优解，活动选择问题具有最优子结构性质。

再比如，在最小生成树问题中，对于一个连通无向图G = (V, E)，假设T是G的一棵最小生成树，e是T中的一条边。如果我们将图G分成两个子图G1和G2，其中G1包含顶点集V1和边集E1，G2包含顶点集V2和边集E2，且e连接V1和V2 。那么T中除去e后，分别在G1和G2中的子树T1和T2，分别是G1和G2的最小生成树。这是因为如果T1不是G1的最小生成树，那么存在一棵更小的生成树T1'，将T1'和T2以及e组合起来，就会得到一棵比T更小的生成树，这与T是G的最小生成树矛盾。所以最小生成树问题也具有最优子结构性质。

6.3 反证法验证

除了判断贪心选择性质和最优子结构性质外，我们还可以使用反证法来验证贪心算法的正确性。反证法的基本思想是：假设所要证明的命题不成立，然后推导出一个矛盾的结论，从而证明原命题成立。

以数组拆分问题为例，给定长度为2n的整数数组nums ，任务是将这些数分成n对(a1, b1), (a2, b2), ..., (an, bn) ，使得从1到n的min(ai, bi)总和最大。我们的贪心策略是先对数组进行排序，然后从第一个位置进行选择，每隔一个选择下一个数。

假设存在一种更优的分法，使得min(ai, bi)总和比我们贪心算法得到的结果更大。那么在这种更优的分法中，必然存在一对数(ai, bi)，使得ai和bi在排序后的数组中的位置不是相邻的（因为我们的贪心策略是相邻选择）。不妨设ai在排序后的数组中的位置为j，bi的位置为k，且j < k，且k - j > 1 。那么在我们的贪心选择中，j位置的数会和j + 1位置的数配对。由于数组是有序的，所以min(ai, bi) <= min(nums[j], nums[j + 1]) 。这就意味着，按照我们的贪心策略得到的结果不会比假设的更优分法差，与假设矛盾。所以我们的贪心算法是正确的。

再比如，在找零问题中，假设我们有面额为1元、5元、10元、20元、50元、100元的纸币，要找零amount元。我们的贪心策略是每次优先选择面额最大的纸币。假设存在一种更优的找零方案，使得使用的纸币数量比我们贪心算法得到的结果更少。那么在这种更优方案中，必然存在某一步没有选择当前最大面额的纸币。比如，当前剩余找零金额为x元，按照贪心算法应该选择面额为y元的纸币（y是小于等于x的最大面额），但在更优方案中选择了面额为z元的纸币（z < y）。那么为了凑够x元，后续需要使用更多的纸币来弥补y - z的差值，这就导致使用的纸币总数会比贪心算法更多，与假设矛盾。所以在找零问题中，贪心算法是正确的。