贪心算法基础：核心思想、最优子结构、贪心选择性质、经典案例
大家好，我是你们的老朋友。今天我们来聊聊贪心算法。
说实话，贪心算法是我个人非常喜欢的一类算法。为什么？因为它「聪明又简单」。你想想看，在复杂问题面前，每一步都选当前最优的，最后居然能得到全局最优解——这听起来是不是有点不可思议？
但别高兴太早。贪心算法不是万能的。它只适用于特定类型的问题。如果乱用，结果会很惨。我在项目中就踩过这个坑，后面会跟大家细说。
贪心算法的核心思想
贪心算法的核心，说白了就八个字：局部最优，全局最优。
什么意思？就是每一步决策时，只考虑当前状态下「最好」的选择，不考虑未来。然后期望这些局部最优的选择，能拼出一个全局最优的解。
举个例子。你去自助餐厅吃饭，每次只拿自己最爱吃的菜。最后你吃到的，大概率是你个人最满意的一餐。这就是贪心思想在生活中的体现。
但在算法世界里，事情没那么简单。贪心算法能成功，必须满足两个条件：最优子结构和贪心选择性质。
最优子结构
最优子结构，听起来很学术。其实很简单：一个问题的最优解，包含其子问题的最优解。
我习惯这样理解：如果你要解决一个大问题，可以先把它拆成几个小问题。如果每个小问题你都用最优的方式解决，那么组合起来就是大问题的最优解。
比如找零问题。你要找36元，面额有25、10、5、1。最优解是「25+10+1」。你会发现，去掉25元后，剩下的11元的最优解是「10+1」。子问题的最优解，正好包含在父问题的最优解里。这就是最优子结构。
重要提醒：最优子结构是贪心算法和动态规划的共同基础。但贪心算法比动态规划多了一个更强的条件——贪心选择性质。
贪心选择性质
贪心选择性质，才是贪心算法的灵魂。它说的是：你可以通过局部最优的选择，来构造全局最优解。
换句话说，你不需要考虑所有子问题。你只需要在当前状态下，选一个看起来最好的，然后继续往前走。剩下的问题，交给递归或迭代去解决。
我曾经在做一个资源调度项目时，一开始用了动态规划。代码写得很复杂，跑起来也慢。后来我发现，这个问题其实满足贪心选择性质。换成贪心算法后，代码量减少了一半，速度提升了10倍。嗯，这就是选对算法的威力。
我的经验：判断一个问题是否能用贪心算法，可以问自己两个问题：
- 当前这一步的最优选择，会不会影响后面的选择？如果不会，大概率可以用贪心。
- 局部最优的累加，是否等于全局最优？如果是，放心用贪心。
经典案例一：找零问题
找零问题是最经典的贪心入门案例。问题描述很简单：给定一些面额的硬币，用最少的硬币数凑出指定金额。
假设我们有面额 25、10、5、1 的硬币。要凑 36 元。
贪心策略：每次选面额最大的硬币，只要不超过剩余金额。
过程如下：
- 剩余 36，选 25 → 剩余 11
- 剩余 11，选 10 → 剩余 1
- 剩余 1，选 1 → 剩余 0
结果：25 + 10 + 1，共 3 枚硬币。
代码实现也很简单：
def coin_change_greedy(coins, amount):
coins.sort(reverse=True) # 从大到小排序
count = 0
for coin in coins:
if amount == 0:
break
num = amount // coin
count += num
amount -= num * coin
return count if amount == 0 else -1
# 测试
coins = [25, 10, 5, 1]
print(coin_change_greedy(coins, 36)) # 输出 3
注意：贪心算法在找零问题上并不总是最优的。如果硬币面额是 [1, 3, 4]，要凑 6 元。贪心会选 4+1+1（3枚），但最优解是 3+3（2枚）。所以，贪心算法依赖于硬币面额的特定组合。我在项目中就遇到过这种「坑」，当时没仔细验证，结果上线后出了 bug。后来我加了一个判断：如果贪心解不是最优，就回退到动态规划。
经典案例二：活动选择
活动选择问题，是贪心算法的另一个经典案例。场景是这样的：你有一个会议室，有很多活动想用。每个活动有开始时间和结束时间。你最多能安排多少个活动？
贪心策略：每次选结束时间最早的活动。为什么？因为结束时间越早，留给后面的时间就越多。
我当年第一次学这个算法时，觉得这个策略太简单了，甚至有点「笨」。但后来在做一个会议调度系统时，我试了各种复杂算法，最后发现——最简单的贪心策略，效果最好。有时候，简单就是美。
来看代码：
def activity_selection(activities):
# activities: [(start1, end1), (start2, end2), ...]
activities.sort(key=lambda x: x[1]) # 按结束时间排序
selected = []
last_end = 0
for start, end in activities:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# 测试
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = activity_selection(activities)
print(result) # 输出 [(1, 4), (5, 7), (8, 11), (12, 14)]
这个算法的时间复杂度是 O(n log n)，主要花在排序上。排序之后，一次遍历就能得到结果，非常高效。
知识体系图
下面我用一张 SVG 图来总结贪心算法的核心知识体系。这张图是我自己画的，希望能帮你理清思路。
总结
贪心算法，说白了就是「短视」的算法。但它之所以能成功，是因为问题本身具有特殊的结构。
我个人建议，遇到一个新问题时，先问问自己：这个问题能不能用贪心？如果能，那就用。如果不能，再考虑动态规划或其他方法。贪心算法的代码量少、效率高，是工程实践中的首选。
但记住：贪心算法不是银弹。一定要验证问题是否满足最优子结构和贪心选择性质。否则，你可能会得到一个「看起来不错，实际上很烂」的解。
好了，今天的内容就到这里。希望你能把贪心算法用起来，解决实际问题。
公众号:蓝海资料掘金营，微信deep3321