最近在团队里带新人做算法训练发现十个人里有八个一上来就问贪心算法是不是就是“每次都选最好的”这个问题问对了一半。贪心算法确实是“每次选当下看起来最好的选择”但它远不止这么简单——难的是你怎么证明“当下最好”加起来就等于“全局最好”。如果不理解这一层遇到真正的面试题或者工程项目里的调度问题很容易踩进“贪心YYDS”的坑里。这篇文章是“贪心算法的应用”系列的第一篇。我打算把贪心算法的底层逻辑和应用案例拆开讲先说清楚贪心算法的本质和适用条件再挑三个最能说明问题的经典应用活动安排、分数背包、找零钱。这几个案例覆盖了贪心算法从“一眼看出正解”到“陷阱重重”的全部场景。无论你是刚开始刷算法题的初学者还是工作中需要写调度、做资源分配的工程师这篇文章都能给你一套可以直接上手的判断方法和代码模板。在工程实践中贪心算法的应用远比教科书写得更普遍。任务调度、网络路由、数据压缩、广告竞价这些领域里处处都有贪心思想的身影。理解贪心不是背几个模板而是建立一种“如何证明局部最优能推出全局最优”的思维习惯。这篇先把地基打牢后面系列文章再聊进阶应用。1. 贪心算法到底在解决什么问题1.1 先搞清楚贪心算法的本质贪心算法的定义一句话就能说清楚在求解问题的每一步都做出当前状态下的最优选择即局部最优希望通过一系列局部最优决策最终得到全局最优解。它和暴力枚举、动态规划最大的区别在于——贪心决策一旦做出就不会回头不会因为后面的情况变化而撤销或者修改前面的选择。这个“不回头”的特性既是贪心算法的效率来源也是它的致命弱点。效率高是因为每一步只做一次比较和选择时间复杂度通常只有 O(n log n) 甚至 O(n)弱点在于如果某个问题不具备“局部最优能推出全局最优”的性质贪心策略就会得到次优甚至错误的答案。我习惯用一个生活化的类比帮助新人理解贪心算法就像走路时只看面前三米的路况每次选择眼前最平坦的三米往前走。如果整条路刚好是“每一段都平坦全程就平坦”还好但如果前面有一小段下坡、后面紧接着上坡只看眼前的走法就可能会绕远路。这就是为什么学习贪心算法不能只学策略还要学会证明策略——不然你就是在赌运气。1.2 贪心算法的两个核心性质要判断一个具体问题能不能用贪心算法解决本质上是在验证两个性质。第一个性质叫做贪心选择性质greedy choice property通过一系列局部最优的选择能够产生全局最优解。翻译成人话就是——在每一个决策点不需要考虑子问题的解只需要做当前看起来最好的选择就够了剩下的子问题依然可以用同样的策略继续求解。第二个性质叫做最优子结构optimal substructure一个问题的最优解包含其子问题的最优解。这两者看起来很像但分工完全不同。最优子结构是所有动态规划问题都具备的性质而贪心选择性质是贪心算法独有的、更强的要求不仅要子问题最优而且每一步的选择本身也可以“贪心地”确定。这里我强烈建议新人把这两个性质写在便签上贴在显示器旁边。根据我这些年带项目的经验90%的贪心算法翻车案例不是因为代码写错了而是没有验证这两个性质就上手写代码。后面案例部分我会带着大家逐个分析每个问题的这两个性质是怎么体现的。1.3 什么样的问题适合用贪心根据经验适合用贪心算法的问题通常有这几个特征问题可以分解成若干步每一步有一个明确的决策点每一步的选择只会影响后续步骤不会影响已经完成的步骤存在一个直观的“局部最优”度量标准比如时间最短、价值最大、成本最小局部最优叠加后能得到全局最优。如果一个需求踩中了以上四点贪心算法往往就是最佳选择。它的实现代码通常短小精悍而且运行效率远高于动态规划和回溯。不过要注意这四个特征只是“看起来像”真正能保证正确性的还是前面说的两个性质尤其是贪心选择性质。工程中我见过太多人拿贪心去解决本质上是资源分配的最优化问题最后在边界情况上翻车。所以遇到具体问题还是要老老实实做性质验证这一步省不得。2. 活动安排问题最经典的贪心入门2.1 问题描述与场景映射活动安排问题是经典算法教材里贪心章节的第一个例子也是我面试别人时最喜欢的考题。问题描述非常接地气假设有一个资源比如会议室若干个活动都想要使用这个资源每个活动有一个开始时间和结束时间如何安排才能让这个资源被利用的活动数量最多这个问题的数学模型叫区间调度问题。每个活动用一个区间 [si, fi] 表示两个活动不冲突的充要条件是区间不重叠即前一个活动的结束时间不超过后一个活动的开始时间。目标是在所有不重叠的区间中选出尽可能多的区间。实际工程里的场景远不止会议室。CPU任务调度、直播间资源分配、广告排期、远程办公的会议室预订系统本质都是区间调度问题。把这个模型吃透很多“看起来很复杂”的业务需求其实都能转化过来。我自己就接过一个直播平台的广告排期需求需求方噼里啪啦讲了一堆业务规则最后抽象出来就是活动安排问题直接用贪心模板半小时就搞定了。2.2 为什么“最早结束优先”是对的活动安排问题有好几种看起来都挺合理的贪心策略按照活动开始时间最早优先按照活动持续时间最短优先按照活动结束时间最早优先按照活动占用资源最少优先。我第一次学的时候直觉上觉得“持续时间最短优先”才对吧毕竟短活动多数量不就多了吗但反例很容易构造一个短活动横跨很长时间比如早上9点到下午5点它虽然持续8小时但它遮挡了无数短活动明显不是最优。正确的贪心策略是按“结束时间最早”排序每次选择结束时间最早且与已选活动不冲突的活动。为什么这个策略是对的核心原因在于在所有活动中选择一个结束时间最早的能够给后续未安排的活动留下最多的时间余量。这个直觉可以用交换论证来严格证明。假设某个最优解中第一个选中的活动不是结束时间最早的那么可以用结束时间最早的活动替换它。因为最早结束的活动结束时间更早替换后依然是合法解而且剩余可安排的区间长度不会变短。反复进行这样的替换就能把任何一个最优解逐步改造成贪心算法得到的解。这就是经典的交换论证exchange argument是证明贪心正确性最重要的工具之一。2.3 完整代码实现与测试活动安排问题的贪心解法代码非常短核心步骤只有三步排序、遍历、选择。def activity_selection(start, finish): # 预计算区间并按照结束时间升序排列 activities sorted(zip(start, finish), keylambda x: x[1]) selected [] last_end -1 for s, f in activities: if s last_end: selected.append((s, f)) last_end f return selected start [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12] finish [4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16] result activity_selection(start, finish) print(result)这里 last_end 记录的是最近一次选中活动的结束时间作为“资源可用时刻”的边界。每次遍历到一个新活动时只需要比较这个活动的开始时间是否大于等于 last_end。整个算法的时间复杂度是 O(n log n)瓶颈在排序遍历阶段是 O(n)。这个模板我在面试和工程项目里用了很多年实测下来很稳。注意一个细节Python 的 sorted 会生成新的列表不会修改传入的 start 和 finish。如果换成 C 或 Java记得先对区间做深拷贝或者直接按下标排序避免污染原始数据。对上面的测试用例代码输出 4 个活动区间分别是 (1,4)、(5,7)、(8,11)、(12,16)。你可以手工验证这确实是最大可选数量因为选满 4 个之后确实没有能和 (12,16) 再叠加的区间了。这道题最大的坑不在遍历逻辑而在排序键选错很多人按开始时间排序写出来边界全乱排查半天才发现问题在第一步。3. 分数背包问题贪心可以直接拿最优解3.1 01背包和分数背包的区别背包问题家族里有两个经常被放在一起比较的问题01背包和分数背包。很多初学者把两者搞混然后用贪心去做01背包结果当然不对然后就得出结论“贪心不能解决背包问题”——这个结论是片面的。区别其实很明确01背包里每件物品只能整体装入或不装分数背包里物品可以按任意比例分割装入比如一袋米可以用掉一半。这个差异直接决定了问题的最优解性质分数背包的最优解可以通过贪心获得而01背包不行01背包需要动态规划。这个区别背后有一个很直观的解释01背包中一件大而重的物品一旦装进去就无法回头局部的“价值密度最高”可能阻塞后续更好的组合而分数背包中既然物品可以分割把当前密度最高的物品尽可能多地装进去永远不会伤害未来的选择所以贪心有效。顺便说一句这个区分在实际业务中特别重要。比如物流装箱货物如果是颗粒状的、可以拆分的就用贪心如果是整件不可拆的冰箱、洗衣机就必须动态规划。不少做采购系统的朋友一开始在这上面栽跟头就是因为没有先判断问题属于哪一类。3.2 单位价值排序的思路分数背包的贪心策略一句话按照单位重量价值从高到低排序依次装入直到背包容量耗尽。这里的“单位重量价值”就是性价比value per unit weight是分数背包的核心度量指标。为什么按性价比而不是总价值排序举个例子一个物品总价值100重量50性价比2另一个物品总价值90重量30性价比3。如果背包只剩25单位容量按总价值排序你会选第一个物品获得50价值按性价比排序会选第二个物品获得75价值。显然性价比是更好的度量。这个策略的正确性同样可以用交换论证证明任何最优解中如果没有优先放入性价比最高的物品则总可以把它和当前占位物品做替换替换后总价值只会增加或不变。反复替换最终得到的就是贪心解。这个证明思路和活动安排问题一脉相承建议读者自己动手推一遍对理解“贪心为什么有效”非常有帮助。3.3 代码演示与参数选择分数背包的代码比活动安排长不了多少def fractional_knapsack(capacity, items): # items: list of (weight, value) items.sort(keylambda x: x[1] / x[0], reverseTrue) total_value 0 for weight, value in items: if capacity weight: total_value value capacity - weight else: total_value value * (capacity / weight) break return total_value items [(10, 60), (20, 100), (30, 120)] capacity 50 print(fractional_knapsack(capacity, items))这里 items 是 (重量, 价值) 的二元组排序键是 value/weight。主循环里先处理“整件能装下”的情况直到遇到第一件装不下的物品把它分割装入剩余容量然后直接跳出循环。计算总价值时用的是比例公式 value * (capacity / weight)这也正是“分数”二字的含义。跑一下这个用例答案是240。计算过程三个物品性价比分别是6、5、4先装(10,60)再装(20,100)剩余容量20装(30,120)的三分之二得到80合计240。注意代码里用除法算性价比在极端情况下会有浮点精度问题。工程上如果要处理大量均匀的小数值物品建议改用交叉相乘排序v1w2 v2w1 代替 v1/w1 v2/w2避免浮点误差影响排序结果。这个细节在计费系统中尤其重要。4. 找零钱问题贪心不是万能的4.1 特定币值下的贪心解法找零钱问题是另一个教科书级案例给定一个金额和若干面额的硬币要求用最少的硬币数量凑出这个金额。比如有1、5、10、25面值的硬币要凑36元贪心策略就是先用大额硬币25元一个10元一个1元一个共3个硬币。在币值设计成“正则系统”的前提下——最直观的就是较大面额能被较小面额整除——贪心找零是能给出最优解的。你回想一下自己日常找零的习惯是不是总先给面额最大的这个人人都会的行为背后就是贪心选择性质。面额之间这种规整的倍数关系让“先拿大额”变成一种天然的正确策略。这个例子特别适合向非技术朋友解释贪心算法。每次用最大的硬币去凑本质就是在做局部最优选择先把当前能减少剩余金额最多的硬币用掉。在正则币值系统下这种选择可以一直递推到全局最优。4.2 会翻车的场景重点来了如果币值系统不正则贪心就会翻车。最著名的反例是1、3、4面值凑6元。贪心算法会先拿4元剩下2元只能用两个1元总共3个硬币但最优解是33两个硬币。差距不大但它实实在在地证明了贪心在这套币值下失效。另一个更夸张的反例是1、15、25面值凑30元贪心先拿25元剩下5元用5个1元总共6个硬币最优解是1515只要2个硬币。这就不是差一个硬币的问题了差距高达4倍。这个例子告诉我们贪心算法高度“场景依赖”同一类问题换一套输入参数结论就从正确变成错误。工程上类似的坑极为常见——你在测试环境里用一套数据验证了贪心没毛病上线后真实数据分布一变问题就暴露了。这也是为什么我反复强调必须理解贪心成立的条件而不是背下“找零钱用贪心”这种表面结论。4.3 何时可以放心使用贪心那么工程里遇到找零这类组合优化问题什么时候可以放心上贪心我的判断标准有三条面额系统满足正则条件较大的币值是较小币值的整数倍或者已经证明在该面额组合下贪心不会产生反例问题规模大但数据范围可控贪心可以在线性或近似线性时间内完成业务允许一定误差或者有把握在业务层面接受贪心与最优解的偏差。严格来说找零钱问题的最优解需要动态规划时间复杂度 O(amount × coinCount)。当 amount 很大时动态规划可能难以承受这时候就需要权衡是用贪心“快但可能不准”还是用动态规划“准确但可能偏慢”。在做这种取舍之前建议先跑一组随机数据对比一下贪心解和最优解的偏差率心里有数再上线。5. 贪心算法的日常排查与避坑经验5.1 贪心常见的四个坑结合我带团队的经验贪心算法写翻车的情况主要集中在四个方面。第一没有验证贪心选择性质就动手。这是最普遍的。看到“找最优”“求最值”就条件反射地写贪心写完才发现跑不过样例。第二排序规则和贪心策略不一致。比如活动安排里按开始时间排序却用结束时间做判断得出的结果必然乱套。第三忽略了边界条件。比如背包容量刚好等于物品总重量、活动时间相同、金额为0这些边界处理不当会输出错误结果。第四用贪心直接替代需要动态规划的问题。某些资源分配、最优组合问题明明不具备贪心选择性质硬套贪心模板结果就是最优解永远差那么一点。这四个坑里第四个最隐蔽。因为测试数据小的时候贪心解和最优解往往恰好重合你根本看不出来。等到了真实数据差距才慢慢浮出水面而那时代码已经上线了。5.2 三招快速验证你的贪心策略那么怎么快速判断一个贪心策略靠不靠谱我这里有一个实战中总结的“三板斧”。第一板斧是构造反例。如果一个问题规模较小可以尝试写一个枚举或动态规划代码在随机小数据上把最优解和贪心解跑一遍比对结果。只要发现一个反例贪心策略就得推翻或加条件。第二板斧是交换论证。从任意一个最优解出发如果能把贪心选择的元素换进去而不降低目标值反复替换直到变成贪心解就可以证明贪心正确。第三板斧是找“单调性”。贪心问题里的决策通常有一个度量且这个度量在一步步决策过程中保持单调比如剩余时间只会减少、剩余容量只会减少这种单调性往往意味着贪心策略是自洽的。这“三板斧”我强烈建议写进自己的算法checklist里。尤其第一板斧成本极低但收益极高。实操中我经常写一个随机测试函数生成上千组小规模数据跑一遍贪心和精确解做对比。例如找零钱的验证代码可以这样写import random def greedy_coin(coins, amount): coins sorted(coins, reverseTrue) count 0 for c in coins: count amount // c amount % c return count def dp_coin(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] # 在1、3、4币值下寻找反例 for _ in range(1000): amount random.randint(1, 200) g greedy_coin([1, 3, 4], amount) d dp_coin([1, 3, 4], amount) if g ! d: print(反例:, amount, 贪心:, g, 最优:, d) break这段代码会在1、3、4币值下很快找到反例比如金额6、9、11等。只要这个测试在几分钟内跑完不报错我就敢在真实数据上用贪心。如果发现问题就用DP兜底或者重新设计策略。5.3 贪心与动态规划的分工最后说说贪心和动态规划的分工这是最多人问的。一个最朴素的分工原则如果一道题满足最优子结构但每一步的最优选择不是“只看当下”能确定的需要记住多种可能性再比较那就要用动态规划。举个例子对比一下同样是“找零钱”在正则币值系统下用贪心在任意币值系统下用动态规划同样是“背包”分数背包用贪心01背包用动态规划。可以说动态规划是“大而全”的通用解法贪心是“小而美”的快速解法。在算法面试里考官出贪心题考察的不是你能不能背出模板而是你能不能一眼判断该用贪心还是动态规划并用一句话给出证明思路。工程实际中我的建议是先想清楚问题的约束条件再决定用哪个。贪心的问题是做不了回溯动态规划的问题是存储开销大、代码量多。能贪心就贪心但在拿不准的时候退一步用动态规划求稳成本往往比你想象的低。毕竟线上系统的稳定性远比那点性能差重要。写到这里贪心算法的三个经典应用也讲得差不多了。最后分享一点我的个人体会贪心算法是那种“看着简单、用着容易翻车”的算法很多初学时候的自信都是靠吃瘪攒出来的。我自己就曾在某个线上调度系统里用过一次未验证的贪心策略好在测试阶段随机数据救了一命从那以后再也不敢跳过性质验证这一步。对想深入的同学建议动手实现一遍活动安排和分数背包的代码再自己构造几个找零钱的反例跑一跑。下一篇系列文章我会接着讲贪心算法在更多场景里的应用哈夫曼编码、最小生成树还有如何用贪心做近似算法。先消化这篇把贪心的“证明思维”练起来后面的案例你会越看越顺。
