想象一下，你去商店买东西，老板找你1元7角零钱。你猜老板会怎么给你？通常他会先给你1个1元硬币（如果有的话），然后是5角，再是1角，尽量用最少的硬币凑够金额。这种“每次都选当前最好的选择，不管未来”的思路，其实就是贪心算法的核心思想。
什么是贪心算法？¶
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的选择（即局部最优解），并希望通过一系列局部最优选择最终得到全局最优解的算法。
简单来说，它就像一个“短视”的决策者：只看眼前的好处，不考虑长远影响。这种策略的关键在于，问题是否满足“贪心选择性质”——即每一步的局部最优选择，最终能导致全局最优。如果满足，贪心算法就能高效解决问题；如果不满足，可能会得到非最优解。
找零钱问题：贪心算法的经典应用¶
找零钱问题是贪心算法最经典的例子。假设我们有以下几种硬币（面额）：25分（quarter）、10分（dime）、5分（nickel）、1分（penny）。现在要找给顾客67分，如何用最少的硬币数量凑齐？
问题分析¶
目标：用最少的硬币凑出67分。
核心思路：从最大面额开始，每次取尽可能多的当前面额，直到金额为0。这种策略在硬币面额满足“任意大面额都不能被更小面额组合出”的情况下（比如25、10、5、1），能保证局部最优，进而全局最优。
具体步骤（以67分为例）¶
- 确定硬币面额：假设硬币按从大到小排序为
[25, 10, 5, 1]。 -
从最大面额开始计算：
- 25分硬币：67 ÷ 25 = 2（最多取2个），2×25=50分，剩余金额：67 - 50 = 17分。
- 10分硬币：17 ÷ 10 = 1（最多取1个），1×10=10分，剩余金额：17 - 10 = 7分。
- 5分硬币：7 ÷ 5 = 1（最多取1个），1×5=5分，剩余金额：7 - 5 = 2分。
- 1分硬币：2 ÷ 1 = 2（最多取2个），2×1=2分，剩余金额：0分。 -
统计总硬币数：2（25分）+ 1（10分）+ 1（5分）+ 2（1分）= 6枚。
验证最优性¶
有没有更少的组合？比如“50分+10分+5分+2分1分”，同样是6枚硬币，没有更少的了。这说明贪心算法在这里确实得到了最优解。
贪心算法的局限性¶
贪心算法并非万能。如果硬币面额不满足“局部最优能推全局最优”，可能会失效。例如：
- 硬币面额：[1, 3, 4]（假设没有2分硬币），目标金额6分。
- 贪心策略：先取4分，剩余2分，取1分×2，共3枚硬币。
- 最优解：取3分×2，共2枚硬币。
这里贪心算法失败了，因为局部最优（取4分）反而导致全局更差。因此，贪心算法只适用于满足“贪心选择性质”的问题——即每一步选择最大面额后，剩下的子问题与整体问题结构相同。
贪心算法的适用场景¶
找零钱问题中，只要硬币面额满足“任意大面额都大于等于所有小面额之和”（比如25、10、5、1，其中10+5+1=16 < 25，5+1=6 < 10，1 <5），贪心就能高效解决。
类似场景还有：
- 活动安排：选择最多不重叠的会议（按结束时间排序，每次选最早结束的活动）。
- 哈夫曼编码：构建最优前缀码（优先合并频率最小的节点）。
总结¶
贪心算法的核心是“局部最优→全局最优”，简单直观，在合适的问题上效率极高。找零钱问题中，只要硬币面额合理，贪心算法能快速得到最少硬币数量。但需注意：贪心算法不保证所有问题都能得到最优解，仅适用于满足贪心选择性质的问题。
下次你遇到“如何用最少步骤完成任务”时，不妨试试贪心思想——从最大面额（或最优起点）开始，每一步选当前最好的选择，说不定就能高效解决问题！