贪心算法：为什么"每次都选最好的"有时候会害了你？
你有没有在食堂打饭时，精准地站到最短的队伍后面，结果旁边那条队的大妈一个人打了六份饭？
那一刻你肯定在心里骂：这破算法，怎么不灵了？
别急，你不是一个人。计算机科学里最"短视"的策略——贪心算法，也经常面临这种尴尬。
贪心：一个"只管当下"的赌徒
贪心算法的核心思想简单到令人发指：每一步都选当前最优的解，从不回头。就像自助餐攻略——第一轮拿最爱的鸡腿，第二轮拿第二爱的薯条，第三轮拿第三爱的蛋糕。你从不考虑营养均衡，只关心"此刻我最想吃啥"。
这种策略最大的优势是快。不需要回溯，不需要动态规划那张复杂的表，一趟遍历往往就能出结果。在很多实际问题里，它甚至能直接给出全局最优解。
但问题来了：它凭什么能？
两大条件：贪心不是万能钥匙
贪心算法能用，必须同时满足两个条件：
- 最优子结构：大问题的最优解包含小问题的最优解
- 贪心选择性质：每一步的局部最优能导向全局最优
第二条尤其关键。用大白话说就是：你选了当下最好的，以后还有机会弥补吗？
我见过太多新手一上来就套贪心，结果碰了一鼻子灰。比如经典的硬币找零反例：假设有1元、3元、4元三种硬币，要凑6元。贪心会先拿4元（最大面额），剩2元，然后拿1元+1元，总共3枚。但最优解明明是3元+3元，只要2枚。
这就像你在食堂选了最短的队伍，结果前面那位是给全宿舍带饭的——你的"局部最优"直接毁了全局。
什么时候贪心真的能赢？
先看一个教科书级的例子：活动选择问题。
周末你有一堆想参加的活动，时间冲突，怎么选才能参加最多？贪心策略很简单：每次选结束时间最早的活动，然后扔掉所有跟它冲突的。
比如：画画(9:00-10:00)、打球(9:30-10:30)、看书(10:00-11:00)。按结束时间排序：画画(10:00)最早，选了它；然后从10:00开始，还能选看书(11:00结束)。总共2个活动。如果你先选了打球，那只能参加1个。
这个例子完美展示了贪心的威力——结束最早的活动给后续留出了最多时间，这种"当前最优"恰好能导向全局最优。
来看一道实战题，正好考察这个思想：
题目： 有N个瓶子，编号1~N，乱序放在架子上。每次可以交换任意两个瓶子，问最少交换几次能让瓶子按1,2,3...N的顺序排列？
样例：
3 1 2 5 4→ 输出3
这道题怎么用贪心？思路是：从左往右扫，每次把当前位置i上本该放的瓶子i换过来。如果位置i上不是i，就找到i在哪里，直接交换。这样每个瓶子最多被交换一次，总交换次数最少。
为什么贪心在这里成立？因为每个位置只需要处理一次，交换当前错误的瓶子不会影响已经排好的位置——局部最优（每次把当前位置修正）就是全局最优。
核心代码就几行：
count = 0
for i in range(1, N+1):
if pos[i] != i:
# 把i换到位置i上
swap(pos[i], pos[pos[i]])
count += 1
每次交换都让至少一个瓶子回到正确位置，这就是贪心选择性质——每步都在减少"错位数"，且不会增加新的错位。
再看一道经典贪心题：排队打水问题。
题目： N个人打水，有M个水龙头，每个人打水耗时不同。如何安排顺序，使所有人的等待时间之和最小？
贪心策略：让打水时间短的人先打。为什么？因为一个人打水时，后面所有人都要等他。让耗时短的人先打，后面等待的人总时间就少。
比如N=7，M=3，打水时间分别为3,6,1,4,2,5,7。排序后是1,2,3,4,5,6,7。分到3个水龙头，每个水龙头的队伍内部按从小到大排。计算等待时间，答案是11。
这个例子里的贪心选择性质很直观：如果你让一个耗时7分钟的人先打，后面6个人每人白等7分钟——这显然不是最优。
什么时候贪心会翻车？
回到开头那个硬币反例。为什么人民币找零用贪心没问题？因为人民币的面额设计刚好满足"后面面额是前面面额的倍数"这种规律（1,2,5,10,20,50,100）。但换成1,3,4这种不规则面额，贪心就废了。
所以用贪心之前，一定要问自己三个问题：
- 我的选择会如何影响后续步骤？
- 有没有可能"当前最优"导致"全局更差"？
- 我能否证明贪心选择不会堵死最优解的路？
如果答案不确定，那大概率需要换动态规划——它会考虑所有可能性，但复杂度往往是指数级的。
新手最容易踩的坑
我批改作业时发现，新手用贪心经常犯这几个错：
第一，不排序直接贪。 找零钱时硬币列表是乱的，不排序就循环，结果先处理了小面额，根本谈不上"贪心"。记住：贪心的前提是"每次选当前最优"，那就必须先让数据有序。
第二，把贪心当万能药。 看到"最少""最多""最短"就往上套。贪心只能解决满足两大条件的问题，其他情况它只会给你一个"差不多"的答案，而不是最优解。
第三，不验证边界条件。 比如找零金额为0、硬币列表为空，这些情况不处理，程序直接崩。
写在最后
贪心算法就像一个目光短浅但行动力极强的决策者。在规则清晰、局部最优能导向全局最优的问题里，它快准狠；但在复杂约束下，它可能让你陷入万劫不复的局部最优。
我的建议是：拿到一个新问题，先别急着写代码。花两分钟想清楚——"我这一步选最好的，后面还有机会弥补吗？" 如果能，大胆用贪心；如果不能，果断换动态规划。
毕竟，人生和算法一样，有些选择可以短视，有些必须放眼全局。区别在于，算法可以重来，人生不行。
