1“贪心”思想

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

适用场景

适用于解决具备贪心选择和最优子结构性质的最优化问题。

贪心选择是指一个问题的整体最优解可通过一系列局部最优解的选择达到，并且每次选择可以依赖以前作出的选择，但不依赖于后面要作出的选择，贪心算法在解决问题时无回溯过程。

最优子结构指的是原问题的最优解包含其子问题的最优解，如果问题不满足此性质，则贪心算法可能无法得到全局最优解。

贪心算法的每一步必须满足：

1.可行性：每次选择都满足问题的核心约束。

2.局部最优：它是当前步骤中所有可行选择中最佳的局部选择。

3.无回溯性：一旦做出选择就不可撤销，不会回头修改之前的决策，减少计算复杂度。

算法边界

贪心算法、动态规划与回溯法同为解决优化或搜索问题的常用策略，却各有不同：贪心算法是 “局部最优主义者”，无回溯地追求每一步的当下最优，计算高效，适合资源分配、活动选择等选择类场景；动态规划则是 “全局规划大师”，会存储子问题结果以避免重复计算，兼顾未来影响并允许局部暂时次优，适合0-1 背包、最长公共子序列等依赖前序状态的问题；回溯法堪称 “穷举探索家”，通过试错穷举、可撤销选择的方式遍历所有可能，适用于需验证所有方案的问题（如全排列、子集和）。

2、算法原理

贪心算法的基本思路是：从问题的某个初始解出发逐步推进，依据特定优化测度，每一步都确保选取局部最优解。算法每步仅考虑一个数据，且所选数据需满足局部优化条件，若下一个数据与当前部分最优解结合后不再构成可行解，则不将其加入部分解中。这一过程持续到所有数据枚举完毕，或无法再添加新数据时，算法便停止。

贪心算法一般按如下步骤进行：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每个子问题求解，得到子问题的局部最优解。

4.将所有子问题的局部最优解合并，形成原问题的一个解。

算法缺陷

1.贪心算法总是求的局部最优解，不能保证整体最优解。

2.贪心算法只能确定某些问题的可行性范围。

3、经典案例

搞懂贪心算法的基本原理后，接下来我们就从图论、组合优化、霍夫曼编码三大领域入手，通过六个经典案例拆解贪心算法的实战用法！小编会同步展示解题代码， 小伙伴们赶紧关注【运筹说】公众号，在后台回复 “贪心算法”，就能免费获取完整代码啦！

Part.1 图论领域经典案例

01 最小生成

在城市基建、网络布线、电路设计等场景中，常遇到“用最低成本连接所有节点”的问题，比如连接4个城市的道路有5种选择，不同路线成本不同，如何选才能让总造价最低且无环路？这就是经典的“最小生成树”问题，今天我们拆解两种基于贪心思想的解决算法：Kruskal算法和Prim算法。

1、什么是“最小生成树”？

最小生成树是指给定无向带权图（顶点=节点，边=连接线路，权重=成本），需生成满足“连通所有顶点+无环路+总权重最小”的子图，子图边数为顶点数减1。如例1：

例1：图中有 4 个节点（V₀、V₁、V₂、V₃），边权重代表节点间的连接成本，如V₀ 到 V₁成本 1、V₀到 V₂成本 2 等，那么该图的最小生成树是什么？

2、两种贪心算法的解题思路

针对上述问题我们适用Kruskal 和Prim 两种贪心算法进行解决。

（1）Kruskal 算法：按成本排序，选路避环路

算法核心：以边为单位，按权值从小到大，用避圈法依次选边，凑够 n-1 条边（n 为节点数）后停止。解题步骤如下：

①列出所有边并按权值从小到大排序：（V0，V1）=1，（V0，V2）=2，（V1，V2）=3，（V1，V3）=4，（V2，V3）=5；

②按照避圈法依次选边：逐个选取权值最小的边，判断是否与已选边构成圈，直到选够3条边：

选边e1=（V0，V1），（e1）无圈，保留，总权重1，生成树边数1；

选边e2=（V0，V2），（e1，e2）无圈，保留，总权重3，生成边数2；

选边e3=（V1，V2），（e1，e2，e3）构成圈，避免环路，跳过；

选边e4=（V1，V3），（e1，e2，e4）无圈，保留，总权重7，生成边数3；

③确定最小生成树与总权值：最小树为T=（e1，e2，e4），总权值为1+2+4=7。

（2）Prim 算法：从单点出发，扩边选最小

算法核心：以“顶点”为核心，从任意顶点开始，选“连接生成树与外部顶点”的最小边，直到包含所有顶点。

①初始化：从任意顶点开始，这个顶点构成最小生成树的初始部分，选择V0做为起始点。

②选最小边：在剩下的顶点中，找到与当前最小生成树中任意顶点相连且权重最小的边，并将其加入到最小生成树中。

③更新集合：将新加入边的另一个端点加入到最小生成树的顶点集合中。

④重复步骤②③，直到所有顶点都被包含在最小生成树中，或者对于非连通图，直到无法再找到满足条件的边为止。即：

初始节点V0，将V0加入生成树，节点数1，无权值；

选边e1=（V0，V1），将V1加入生成树，节点数2，权值1；

选边e2=（V0，V2），将V2加入生成树，节点数3，权值3；

选边e4=（V1，V3），将V3加入生成树，节点数4，权值7，终止。

⑤最终最小树为T=（e1，e2，e4），总权值为1+2+4=7。

（3）Kruskal 算法和Prim 算法的对比

3、简单代码实现

以上述例题为例，借助Python语言实现最小生成树求解。

（1）Kruskal 算法

运行结果如下：

（2）Prim 算法

运行结果

02 单源最短路径

导航避堵找近路、快递规划配送线，其实都在解决“单源最短路径”问题，简单说就是从一个起点出发，算出到其他所有节点的最短距离，而这个实用的问题，用 Dijkstra 贪心算法就能轻松搞定～

1、什么是“单源最短路径”？

单源最短路径问题是指：给定一个带权有向图（或无向图），以某个节点为起点，计算该起点到图中所有其他节点的“最短路径权重总和”。如例2：

例2：图中有5个节点（A-E），边权重代表节点间的距离（或时间、成本），如A到B距离4、A到C距离2，那么从A出发到B、C、D、E的最短距离是多少？

2、Dijkstra算法的解题思路

针对上述问题我们使用Dijkstra算法贪心算法进行解决。Dijkstra算法的核心是“每次选择当前距离起点最近的未访问节点”，通过局部最优逐步推导全局最优，步骤如下（以起点A为例）：

①初始化距离：起点A的距离设为0，其他节点（B、C、D、E）距离初始化为无穷大（表示暂未可达）；

②筛选最近未访问节点：在所有未访问的节点中，找出“当前距离起点最近的节点”（首次直接选中起点A）；

③更新邻居距离：以当前选中的节点为中介，计算起点经该节点到其所有邻居节点的新距离（新距离=当前节点距离+当前节点到邻居的边权），若新距离更短则更新；

④标记已访问：将当前完成距离更新的节点标记为已访问，避免后续重复筛选和更新；

⑤重复步骤②-④：持续在未访问节点中筛选距离起点最近的节点、更新其邻居距离、标记访问状态，直到所有节点均被访问，最终得到起点到所有节点的最短距离。即：

首次执行②-④：选中起点A（距离0），更新A到B为4、A到C为2，标记A已访问；

第一次循环：从未访问节点中选中C（距离2），更新A到D为10、A到E为12，标记C已访问；

第二次循环：从未访问节点中选中B（距离4），更新A到D为9（比原10更短），标记B已访问；

第三次循环：从未访问节点中选中D（距离9），更新A到E为11（比原12更短），标记D已访问；

第四次循环：从未访问节点中选中E（距离11），E无邻居无需更新距离，标记E已访问，此时所有节点均已访问，终止。

⑥最终最短距离与路径：A→A（0）、A→B（4）、A→C（2）、A→D（9，A→B→D）、A→E（11，A→B→D→E）。

3、简单代码实现

以上述例题为例，借助Python语言实现最短路径求解。

Dijkstra算法

运行结果如下：

Part.2 组合优化领域经典案例

01 活动选择问题

“下午2点的项目会议、3点的客户面谈、4点的团队培训……”打开日程表，密密麻麻的活动挤在一起，总担心错过重要安排？其实这个看似复杂的“时间管理难题”，用贪心算法就能轻松解决！

1、什么是“活动选择问题”？

简单来说，活动选择问题就是给定一组活动，每个活动包含开始时间、结束时间和唯一标识，在同一时间只能进行一个活动的前提下，选择出最多不冲突的活动。如例3：

例3：我们有11 个活动要集中举办，却只有一个会场（同一时间只能开展一场活动），怎么选才能让最多活动顺利落地、不冲突？

2、贪心算法解题思路

贪心算法的关键是“每次选当下最优”，这里的策略超简单：

①活动排序：将 11 个活动按结束时间从早到晚排序（结束时间相同可任意排列），排序结果为 A→B→C→D→E→F→G→H→I→J→K；

②初始化状态：选中活动列表为空，记录 “上一入选活动结束时间” 为 0（初始无活动）；

③逐活动筛选：

选活动 A：开始时间 1≥0，不冲突，入选，更新结束时间为 4，选中数 1；

选活动 B、C：开始时间 ＜4，冲突，跳过；

选活动 D：开始时间 5≥4，不冲突，入选，更新结束时间为 7，选中数 2；

选活动 E、F、G：开始时间 ＜7，冲突，跳过；

选活动 H：开始时间 8≥7，不冲突，入选，更新结束时间为 11，选中数 3；

选活动 I、J：开始时间 8＜11，冲突，跳过；

选活动 K：开始时间 12≥11，不冲突，入选，更新结束时间为 16，选中数 4；

④结果：选中活动为 A、D、H、K，共 4 个，是最多不冲突的活动组合。

3、简单代码实现

以上述例题为例，借助Python语言实现活动选择求解。

运行结果如下：

02 钱币找零问题

收银台找零37分，是拿“1个25分+1个10分+2个1分”（共4枚），还是“3个10分+7个1分”（共10枚）？显然前者更方便—其实这就是贪心算法能解决的“钱币找零问题”！

1、什么是“钱币找零问题”？

给定一组硬币面额和目标找零金额，用最少的硬币数量凑出目标金额，就是钱币找零问题的核心需求。如例4：

例4：假设我们有硬币面额[25,10,5,1]美元，现需找零37分，怎样使用最少硬币凑出37分？

2、贪心算法解题思路

钱币找零问题和活动选择问题的“按结束时间排序”逻辑相通，这里的贪心策略也围绕“排序+优先选最优”：

①面额排序：将硬币面额按从大到小排序，结果为 25 分→10 分→5 分→1 分；

②初始化状态：选中硬币组合为空，剩余待凑金额记为 37 分；

③逐面额凑零：

25 分：37÷25=1 枚（余 12 分），入选 1 枚，剩余金额更新为 12 分；

10 分：12÷10=1 枚（余 2 分），入选 1 枚，剩余金额更新为 2 分；

5 分：2＜5，无法使用，跳过；

1 分：2÷1=2 枚（余 0 分），入选 2 枚，剩余金额更新为 0 分；

④结果：选中 25 分 ×1+10 分 ×1+1 分 ×2，共 4 枚硬币，凑出 37 分，为最少硬币组合。

3、简单代码实现

以上述例题为例，借助Python语言实现钱币找零问题求解。

运行结果如下：

关键提醒

注意！贪心不是“万能找零法”只有满足“大面额是小面额的倍数”的硬币组合（如[25,10,5,1]、[10,5,1]），贪心算法才有效。

比如若面额是[1,3,4]、目标金额6：贪心会选“4+1+1”（3枚），但最优解是“3+3”（2枚）——这时贪心就失效了！

03 部分背包问题

周末露营背包容量有限（50kg），想带的装备又多又重？其实“有限容量装最大价值”的问题，用部分背包的贪心算法就能解决！

1、什么是“部分背包问题”？

给定一组可分割的物品（含重量、价值、标识）和固定容量的背包，在总重量不超容量的前提下，选出总价值最大的物品组合（可装部分物品，价值按比例计算）。如例5：

例5：假设有背包总容量为50kg，有以下物品需要装进背包，怎样可以选出总价值最大的物品组合？

2、贪心算法解题思路

贪心算法解决部分背包问题的核心思路是按“价值密度”排序装货，解题步骤如下：

①价值密度排序：计算各物品价值密度（价值 ÷ 重量），按降序排序，结果为 A（6.0 元 /kg）→B（5.0 元 /kg）→C（4.0 元 /kg）；

②初始化状态：背包剩余容量记为 50kg，选中物品组合为空，总价值初始为 0 元；

③逐物品装载：

物品 A（10kg，60 元）：剩余容量≥10kg，全装，总价值 + 60 元，剩余容量更新为 40kg；

物品 B（20kg，100 元）：剩余容量≥20kg，全装，总价值 + 100 元，剩余容量更新为 20kg；

物品 C（30kg，120 元）：剩余容量 20kg＜30kg，装20/30=2/3，总价值+ 80元（120×2/3），剩余容量更新为 0kg；

④结果：选中 A 全装 + B 全装 + C 装 2/3，总重量 50kg，总价值 240 元，为最大价值组合。

3、简单代码实现

以上述例题为例，借助Python语言实现部分背包问题求解。

运行结果如下：

关键提醒

注意！部分背包可分割，贪心算法最优。0-1背包物品不可分割，贪心可能失效，需用动态规划解决。

Part.3 霍夫曼编码

霍夫曼编码问题

想保存一篇长文本，却发现手机存储告急？或者传输文件时，因为体积太大速度慢吞吞？其实文本压缩的核心秘诀之一，就是贪心算法家族的“霍夫曼编码”——它能给高频出现的字符分配短编码，低频字符分配长编码，在不丢失信息的前提下大幅缩减文件体积！今天就以经典文本“ABRACADABRA”为例，拆透霍夫曼编码的实现逻辑。

1、什么是“霍夫曼编码问题”？

霍夫曼编码是一种无损数据压缩算法，核心目标是通过“不等长编码”减少文本的总存储位数。它遵循两个关键原则：

（1）高频短码：出现次数多的字符（如“ABRACADABRA”中的“A”），分配更短的二进制编码（如“0”）；

（2）无歧义解码：任何字符的编码都不是其他字符编码的前缀（避免解码时混淆，比如“A”编为“0”，则其他字符编码不能以“0”开头）。

例6：以“ABRACADABRA”为例，传统ASCII编码给每个字符分配8位二进制数，总长度为11×8=88位；而通过霍夫曼编码，总长度可缩减至23位，压缩率高达26.14%，那么如何实现霍夫曼编码呢？

2、贪心算法解题思路

贪心算法解决霍夫曼问题的核心是“构建霍夫曼树”，靠“每次合并频率最低的字符”实现：

①统计字符频率：算每个字符出现次数，即A:5、B:2、R:2、C:1、D:1；

②构造霍夫曼树：将每个字符作为一个独立的节点，节点权重为该字符在字符串中的出现频率，将这些节点按权重升序排序后，反复选取权重最小的两个节点合并为新节点，新节点权重为两子节点之和，将新节点加入集合并重新排序，直至所有节点合并为一个根节点，霍夫曼树构建完成，霍夫曼树构建过程如图所示：

③进行 01 编码：依据最终生成的霍夫曼树，遵循 “左分支为 0、右分支为 1” 的编码规则，从根节点到每个字符叶子节点的路径即为该字符的霍夫曼编码，最终得到编码结果：A：0 、D：100 、C：101 、R：110 、B：111 ；

④生成最终码文：用各字符对应的霍夫曼编码逐字符替换原字符串 “ABRACADABRA”，得到最终码文为：01111100101010001111100；

⑤ 计算压缩效果：统计霍夫曼编码总长度，计算公式为1×5+3×1+3×1+3×2+3×2=23位，传统 ASCII 编码总长度为 11×8=88 位，因此压缩率为（23÷88）×100%=26.14%。

3、简单代码实现

以上述例题为例，借助Python语言实现霍夫曼编码。

运行结果如下：

实际运用

霍夫曼编码可以被应用到如下领域：

文件压缩：ZIP、RAR等压缩软件的核心算法之一；

网络传输：减少数据量，加快传输速度；

多媒体压缩：JPEG图像、MP3音频等都用到类似思想。

4、总结

贪心算法的核心是“局部最优→全局最优”，但需满足贪心选择性质和最优子结构性质。本文6大经典案例覆盖图论、组合优化、数据压缩三大领域，虽解题思路各有侧重，但均遵循“定义局部最优标准→迭代选择→整合结果”的核心框架。

在实际应用中，需先判断问题是否适合贪心算法，若不适合则改用动态规划等其他算法。掌握这些经典案例，能帮助你快速解决各类资源优化、路径规划、数据处理问题。

END

作者 | 李超凡 孟婷

责编 | 邱宇

审核 | 徐小峰