1. 贪心算法入门从生活场景到代码实现第一次听说贪心算法这个概念时我正坐在大学食堂里纠结该选哪些菜。预算只有20元但想吃的红烧肉要18元青菜5元鸡腿8元鱼香肉丝12元...如何在有限的预算内吃到最满意的组合这种看似简单的日常决策恰恰体现了贪心算法的核心思想——在每一步选择中都采取当前看来最优的决策希望最终达到全局最优。贪心算法(Greedy Algorithm)是算法设计中一种重要的思想方法它通过局部最优选择来构建全局解。与动态规划不同贪心算法不会回退已做的选择这使得它在很多问题上具有更高的效率。举个典型例子假设我们要用最少数量的硬币凑出36元现有1元、5元、10元、20元四种面额。贪心策略会先选最大的20元剩下16元再选10元最后选5元和1元总共4枚硬币。这个每次选最大面额的策略在这个案例中确实得到了最优解。def coin_change_greedy(amount, coins[20, 10, 5, 1]): coins.sort(reverseTrue) count 0 for coin in coins: while amount coin: amount - coin count 1 return count注意硬币问题使用贪心算法能得到最优解的前提是硬币面额具有特定关系如倍数关系。如果硬币面额为1、3、4元要凑6元时贪心会选择411共3枚而最优解其实是332枚。2. 贪心算法的适用条件与经典问题2.1 贪心选择性质与最优子结构贪心算法并非万能钥匙它能够正确解决问题的前提是问题具备两个关键性质贪心选择性质(Greedy Choice Property)问题的全局最优解可以通过一系列局部最优选择得到。这意味着我们不需要考虑子问题的解只需做出当前最优选择。最优子结构(Optimal Substructure)问题的最优解包含其子问题的最优解。这与动态规划相同但贪心算法更大胆它不需要知道所有子问题的解。以经典的活动选择问题为例假设有一系列活动每个活动有开始和结束时间如何选择最多数量的互不冲突的活动贪心策略是按照结束时间排序每次选择结束最早且不与已选活动冲突的活动。这个策略之所以有效正是因为该问题满足上述两个性质。def activity_selection(start, finish): activities list(zip(start, finish)) activities.sort(keylambda x: x[1]) # 按结束时间排序 selected [activities[0]] for act in activities[1:]: if act[0] selected[-1][1]: # 检查是否冲突 selected.append(act) return selected2.2 典型贪心算法问题集锦除了硬币问题和活动选择问题贪心算法还适用于以下经典场景霍夫曼编码用于数据压缩通过构建最优前缀码来最小化编码长度最小生成树(Prim/Kruskal算法)在加权连通图中找到连接所有顶点的最小权重边集Dijkstra算法解决单源最短路径问题区间调度问题与活动选择类似但有多种变体如加权区间调度分数背包问题物品可分割时的背包问题最优解下表对比了几个典型问题的贪心策略问题类型贪心策略时间复杂度是否总能得到最优解硬币问题每次选最大面额O(n)取决于硬币面额活动选择选结束最早的活动O(nlogn)是分数背包按价值密度排序O(nlogn)是0-1背包同上-否最小生成树选最小权重边O(ElogV)是3. 贪心算法的局限性及应对策略3.1 何时贪心策略会失效虽然贪心算法简洁高效但它并非放之四海而皆准。最典型的反例是0-1背包问题给定一组物品每个有重量和价值在背包容量限制下如何选择物品使总价值最大如果尝试用贪心策略按价值密度从高到低选择可能会错过全局最优解。假设背包容量为50物品如下物品A重量10价值60密度6物品B重量20价值100密度5物品C重量30价值120密度4贪心策略会选择AB总价值160但最优解其实是BC总价值220。这个例子清晰地展示了贪心算法的局限性——局部最优不等于全局最优。3.2 贪心与动态规划的抉择当贪心算法失效时动态规划(DP)通常是更好的选择。二者的核心区别在于选择回退贪心算法一旦做出选择就不会改变DP会考察所有可能性子问题解贪心算法不保存子问题解DP会存储并复用效率贪心通常更高效DP可能计算冗余子问题决策时应考虑如果问题满足贪心选择性质优先用贪心更高效如果问题有明显的重叠子问题考虑DP可以先用贪心尝试验证是否能得到最优解实用技巧在面试或竞赛中当问题看起来像背包问题时先确认是否物品可以分割分数背包用贪心0-1背包用DP。这是常见的考点陷阱。4. 贪心算法实战从LeetCode到工程应用4.1 LeetCode经典贪心题目解析跳跃游戏(LeetCode 55)给定一个非负整数数组你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。贪心策略维护一个可达的最远位置遍历时更新这个值。如果最远位置超过数组长度则成功。def canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach len(nums) - 1: return True return True加油站问题(LeetCode 134)在环形路上有N个加油站每个站的油量gas[i]和到下一站的耗油量cost[i]。判断从哪个站出发可以绕完一圈。贪心策略如果总油量总耗油量则一定有解。从起点出发当剩余油量0时重置起点为下一站。def canCompleteCircuit(gas, cost): total_tank curr_tank start 0 for i in range(len(gas)): total_tank gas[i] - cost[i] curr_tank gas[i] - cost[i] if curr_tank 0: start i 1 curr_tank 0 return start if total_tank 0 else -14.2 工程中的贪心算法应用在实际工程中贪心算法常用于任务调度系统如Hadoop的任务分配选择当前最空闲的节点缓存淘汰策略LRU(最近最少使用)就是一种贪心策略网络路由Dijkstra算法用于路由选择资源分配如云计算中的虚拟机部署以微服务限流为例当系统过载时需要选择哪些请求丢弃。一种贪心策略是优先丢弃对业务影响最小的请求如可重试的读请求保留关键事务请求。这种策略虽然简单但在实际中往往能取得不错的效果。我在实际项目中曾用贪心算法解决过一个文件分片上传的调度问题。需要将大文件分片上传到多个存储节点每个节点的上传速度和剩余空间不同。贪心策略是每次选择当前上传速度最快且剩余空间足够的节点这显著提高了整体上传效率。虽然理论上可能存在更优的调度方案但在实际业务场景中这种简单高效的策略已经足够好——这也是工程中常说的足够好的解决方案优于完美的理论解。