贪心算法：那些"目光短浅"的选择，凭什么能赢？
你有没有在超市收银台前做过这样的决定——手里攥着一张100块，买瓶3块5的矿泉水，收银员问"有没有零钱"，你翻了翻口袋，掏出一把硬币，先挑面值最大的往外递？
这个动作太自然了，自然到你根本不会去想：为什么先递大面额的硬币，最后凑出来的硬币总数往往最少？更不会去想：这个策略在什么情况下会翻车？
但就是这么一个"目光短浅"的直觉，背后藏着一个在算法世界里既简单又危险的家伙——贪心算法。
贪心不是"聪明"，是"不回头"
很多人第一次接触贪心算法时，会把它理解成"聪明的算法"。这个理解有偏差。
贪心的本质不是聪明，而是不回头。
它每一步只做一件事：在当前这个瞬间，从所有可选项里挑出看起来最好的那个，然后——注意这个"然后"——永远不再回头看。它不会想"我如果现在不选这个，后面会不会有更好的组合"，也不会想"我刚才那个选择是不是错了，要不要撤销重来"。
这种"不回头"的性格，让贪心算法极其高效。大多数贪心算法只需要一次遍历，时间复杂度往往是 O(n) 或者 O(n log n)（排序的代价）。对比动态规划那种需要枚举所有子问题、填一张二维表的做法，贪心简直快得离谱。
但"不回头"也意味着一个致命风险：你可能会走进一条死胡同，而且永远不知道另一条路其实更好。
所以，贪心算法的核心问题从来不是"怎么写代码"，而是"这个问题配不配用贪心"。
两个条件，决定贪心能不能用
一个问题是够能用贪心，要看它是否同时满足两个性质：
第一，最优子结构。 大白话就是：大问题的最优解，能由小问题的最优解拼出来。这个条件很多问题都满足，动态规划也依赖它。
第二，贪心选择性质。 这才是分水岭。它的意思是：你每一步选当前最好的，最终一定能得到全局最优，而且你不需要为"以后"留后路。
第二个条件听起来很玄，但验证它的方法其实很朴素——问自己：我现在选最好的，会影响后面选最好的吗？如果不会，贪心大概率成立；如果会，贪心大概率翻车。
举个最经典的翻车案例。硬币面额是 1、3、4，要凑 6 块钱。贪心先选 4，剩下 2，只能两个 1，总共 3 枚。但最优解是 3+3，2 枚。问题出在哪？出在"选 4"这个动作，把"凑出 3 的倍数"这个可能性给堵死了。你当下的最优，破坏了未来的最优。
而人民币的面额 1、2、5、10 之所以能用贪心，是因为每个面额都是前一个的倍数关系，选大面额永远不会让你"凑不齐"或者"需要更多硬币"。
一道题看清贪心的"排序依赖"
来看一个很能说明问题的题目：交换瓶子。
有 N 个瓶子，编号 1 到 N，现在乱序摆在架子上，比如 3 1 2 5 4。每次你可以交换任意两个瓶子的位置，问至少交换多少次能让它们归位成 1 2 3 4 5。
这道题在考察什么？表面上是"最少交换次数"，本质上是在考察置换环的分解，而贪心思想恰好能优雅地解决它。
思路是这样的：最终状态是每个位置 i 上放着编号 i 的瓶子。如果某个位置的瓶子不对，那它一定属于某个"环"——比如位置 1 上放着 3，位置 3 上放着 2，位置 2 上放着 1，这就构成了一个 1→3→2→1 的环。
关键洞察是：一个长度为 k 的环，最少需要 k-1 次交换就能复原。 为什么？因为每次交换最多让一个瓶子归位，而环里的 k 个瓶子，最后一个会"自动"归位，所以只需要 k-1 次。
那贪心在哪里？贪心的策略是：从左到右扫描，只要当前位置的瓶子不对，就和它应该在的位置上的瓶子交换。这个操作每次至少让一个瓶子归位，而且不会破坏已经归位好的瓶子。
# 核心逻辑
for i in range(1, n+1):
while bottles[i] != i:
# 把位置 i 上的瓶子，换到它该去的位置
target = bottles[i]
bottles[i], bottles[target] = bottles[target], bottles[i]
swaps += 1
你看，这里没有复杂的搜索，没有回溯，就是"发现不对就换到对的位置"。为什么这样贪心是对的？因为每次交换都让至少一个瓶子永久归位，而且不会让任何已经归位的瓶子重新错位。局部最优（每次让一个瓶子归位）累积起来，就是全局最优。
这道题完美体现了贪心的一个前提：操作之间没有"负作用"。你做的每一步好事，都不会抵消掉之前做的好事。
另一道题：贪心需要"排序"来保驾护航
再看一道更贴近生活的题：打水问题。
N 个人要打水，有 M 个水龙头，第 i 个人打水需要 Ti 时间。怎么安排才能让所有人的等待时间之和最小？
这道题在考察什么？考察的是排序 + 贪心分配的组合。
先想一个简化版：只有 1 个水龙头，N 个人排队。怎么排等待时间最小？答案是按打水时间从小到大排。为什么？因为打水快的人先上，后面所有人的等待时间都会缩短。这是一个经典的贪心结论：短作业优先。
现在有 M 个水龙头，怎么办？贪心的思路是：把打水时间从小到大排序，然后依次分配给当前"最早空出来"的水龙头。 这就像你排队打饭时，总是看哪条队伍最短就往哪站——只不过这里"队伍长度"是用累计时间衡量的。
# 排序后，依次把每个人分配到当前累计时间最小的水龙头
times.sort()
faucets = [0] * m # 每个水龙头的累计时间
total_wait = 0
for t in times:
# 找到当前累计时间最小的水龙头
idx = faucets.index(min(faucets))
total_wait += faucets[idx] # 这个人的等待时间
faucets[idx] += t # 更新该水龙头的累计时间
注意这里的贪心是"双层"的：先通过排序保证短作业优先，再通过每次选累计时间最小的水龙头来平衡负载。每一步都在选"当前最好"，而且这个选择不会让后续变差——因为把短时间的人安排到空闲的水龙头，只会让整体等待时间更小。
这道题和交换瓶子一样，贪心之所以成立，是因为每个决策都是独立的、不可逆的、且不会互相拖后腿。
什么时候该对贪心说"不"
我见过太多人，学完贪心之后，看什么题都想用贪心。这是很危险的。
判断标准其实很简单：如果你需要"撤销"之前的某个选择才能得到更优解，那贪心就不适用。
比如找零钱问题，如果硬币面额是 1、3、4，凑 6 块，贪心选了 4 之后发现剩下 2 块只能用两个 1，这时候你心里会想"要是刚才不选 4 就好了"——这个"要是"就是贪心失效的信号。
这时候就该请出动态规划了。动态规划会老老实实地枚举所有可能性，虽然慢，但保证正确。
所以我的建议是：先用贪心试，如果发现需要"回头"，立刻切换到动态规划。 贪心是效率最高的方案，但不是万能的。知道什么时候不用它，比知道怎么用它更重要。
写在最后
贪心算法给我的最大启发，其实不是算法本身，而是一种决策哲学：在信息不完全、时间有限的情况下，选择当前最优解，往往比追求全局最优更现实。
当然，前提是你得判断清楚——这个决策会不会让你走进死胡同。
如果你想进一步深入，我建议你沿着三个方向走：一是学习交换论证法，这是证明贪心正确性的核心工具；二是对比学习动态规划，理解两者在"是否回头"上的本质差异；三是多刷区间调度类的题目，这类问题是贪心思想最密集的练兵场。
关于作者
我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。
这些年累计帮助 多名 学生通过编程特长升入自己心仪的目标学校。
如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）