Hello Algo 贪心算法章节总复习贪心选择性质、三步解题框架与三大经典贪心问题的正确性证明【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文是对《Hello 算法》本仓库英文文档树en/docs/chapter_greedy/贪心算法章节章末总复习Summary的深度展开。它以官方小结的九条核心结论为主线把什么是贪心、贪心什么时候可靠、如何设计并证明贪心策略讲透并通过零钱兑换、分数背包、最大容量、最大切分乘积四个经典问题串起从策略推导到反证法证明的完整链路。读完你将掌握贪心算法与动态规划的本质区别、判断问题是否适用贪心的两大性质以及一套可复用的分析 → 定策略 → 证正确解题方法论。1. 章节总览这章在讲什么贪心算法Greedy Algorithm是求解最优化问题的常用方法其基本思路是在每个决策阶段选择当前看起来最好的选项即贪心地做出局部最优决策以期最终得到全局最优解。它实现简单、求解高效被广泛用于大量实际问题。本章小结summary.md把整章知识收敛为如下几条核心结论贪心算法通常用于求解最优化问题核心原理是在每个决策阶段做局部最优决策以期获得全局最优解贪心算法逐轮做贪心选择每轮把原问题转化为一个规模更小的子问题直到问题被解决贪心算法不仅实现简单求解效率也高相比动态规划通常拥有更低的时间复杂度在零钱兑换问题中某些硬币组合下贪心能保证最优解另一些组合下贪心可能得到很差的结果适合贪心求解的问题具备两大性质贪心选择性质与最优子结构其中贪心选择性质代表了贪心策略的有效性对复杂问题证明贪心选择性质并不简单相对而言证伪它更容易例如零钱兑换问题贪心解题主要有三步问题分析、确定贪心策略、正确性证明其中确定策略是核心正确性证明常是主要难点分数背包在 0-1 背包基础上允许选取物品的一部分因此可以用贪心求解其正确性可用反证法证明最大容量问题可用穷举法以 $O(n^2)$ 求解通过每轮向内侧移动较短板的贪心策略可优化到 $O(n)$最大切分乘积问题依次推导出两条贪心策略$\geq 4$ 的整数都应继续拆分、最优拆分因子是 $3$其时间复杂度取决于幂运算的实现方式通常为 $O(1)$ 或 $O(\log n)$。以上每一条都会在后续小节展开。对应章节正文分别位于 greedy_algorithm.md贪心算法总论、fractional_knapsack_problem.md分数背包问题、max_capacity_problem.md最大容量问题、max_product_cutting_problem.md最大切分乘积问题。2. 贪心算法是什么与动态规划的分野贪心算法与动态规划都常用于求解最优化问题两者都依赖最优子结构性质但工作方式截然不同动态规划在做出当前决策时会考虑之前的所有决策用过去子问题的解来构造当前子问题的解贪心算法不考虑过去的决策而是向前做出贪心选择不断缩小问题规模直到问题被解决。为了直观理解贪心的工作方式章节正文以零钱兑换问题切入该问题在完全背包章节中已做过介绍。贪心策略为每次选择不超过目标金额、且最接近目标金额的那枚硬币重复此步骤直到凑齐目标金额。仓库实现见 coin_change_greedy.pydef coin_change_greedy(coins: list[int], amt: int) - int: Coin change: Greedy algorithm # Assume coins list is sorted i len(coins) - 1 count 0 # Loop to make greedy choices until no remaining amount while amt 0: # Find the coin that is less than and closest to the remaining amount while i 0 and coins[i] amt: i - 1 # Choose coins[i] amt - coins[i] count 1 # If no feasible solution is found, return -1 return count if amt 0 else -1贪心优势简单高效。若硬币最小面额为 $\min(coins)$贪心选择的循环最多执行 $amt / \min(coins)$ 次时间复杂度约为 $O(amt / \min(coins))$远低于动态规划解法的 $O(n \times amt)$。贪心局限某些硬币组合下无法得到最优解。下图展示了两个反例正例 $coins [1, 5, 10, 20, 50, 100]$该硬币组合下贪心对任意 $amt$ 都能找到最优解反例 $coins [1, 20, 50]$设 $amt 60$贪心只能找到 $50 1 \times 10$共 11 枚而动态规划能找到 $20 20 20$仅 3 枚反例 $coins [1, 49, 50]$设 $amt 98$贪心只能找到 $50 1 \times 48$共 49 枚而动态规划能找到 $49 49$仅 2 枚。以上反例在 coin_change_greedy.py 的驱动代码中均有对应测试数据。因此对零钱兑换这类问题贪心无法保证全局最优甚至可能产生很差的结果更适合用动态规划求解。总体而言贪心算法适用于两类场景能保证最优解此时贪心往往是最佳选择因为其效率通常优于回溯和动态规划能找到近似最优解对很多复杂问题求全局最优非常困难能高效求得次优解已是很好的结果。3. 适用条件贪心选择性质与最优子结构什么样的问题适合贪心相较动态规划贪心算法的适用条件更严格主要考察两大性质贪心选择性质只有当局部最优选择总能导向全局最优解时贪心才能保证得到最优解最优子结构原问题的最优解包含子问题的最优解该性质在动态规划章节已详细介绍此处不再展开。其中贪心选择性质是判断核心它直接代表了贪心策略的有效性。然而实践中证明它并不容易。在零钱兑换问题中虽然很容易举出反例来证伪贪心选择性质但要证明某组硬币在什么条件下贪心恒成立却困难得多——通常只能凭直觉或举例给出模糊答案难以给出严谨数学证明。章节正文提到学界有一篇论文给出了判定硬币集合对任意金额是否可被贪心最优求解的 $O(n^3)$ 算法Pearson, D.,A polynomial-time algorithm for the change-making problem, Operations Research Letters, 2005。4. 贪心解题三步框架贪心问题的一般求解过程可归纳为三步问题分析梳理并理解问题特征包括状态定义、优化目标和约束条件这一步骤同样出现在回溯与动态规划中确定贪心策略决定每一步如何做贪心选择策略应让问题规模逐步缩小最终解决整个问题正确性证明通常需要证明问题同时具备贪心选择性质与最优子结构可能要借助数学归纳法或反证法。其中确定贪心策略是核心步骤实践中却并不容易原因主要有二策略因问题而异很多问题的贪心策略相当直观可凭粗略推理与试验得出但对复杂问题策略可能隐藏很深十分考验解题经验与算法功底部分策略极具欺骗性我们可能信心满满地设计策略、写出代码并提交却仍有测试用例失败——因为该策略只是部分正确零钱兑换就是典型例子。为了保证正确性应对贪心策略做严格数学证明通常采用反证法或数学归纳法若证明暂无头绪也可退一步通过针对测试用例的调试来逐步修正、验证贪心策略。章节正文还给出了典型的贪心适用问题清单区间调度总是选最早结束的任务、分数背包总是选单位价值最高的物品、股票交易多次交易、先卖后买、利润最大化、哈夫曼编码每次合并频率最低的两个节点得到最小带权路径长度、Dijkstra 算法非负权图单源最短路径等。5. 典型案例一分数背包问题问题定义给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$背包容量为 $cap$。每个物品只能选一次但可以选取其一部分价值与选取重量成正比求容量约束下能装入背包的最大总价值。分数背包与 0-1 背包整体结构非常相似状态同样包含当前物品 $i$ 与容量 $c$关键区别在于允许按比例切割物品物品 $i$ 的单位重量价值为 $val[i-1] / wgt[i-1]$称为单位价值若装入物品 $i$ 中重量为 $w$ 的部分则背包获得的价值为 $w \times val[i-1] / wgt[i-1]$。贪心策略最大化总价值本质上是优先放入单位价值更高的物品。由此得出三步策略——按单位价值从高到低排序逐轮贪心选择当前单位价值最高的物品若剩余容量不足则取当前物品的一部分装满背包。仓库实现见 fractional_knapsack.py。代码定义了一个Item类以便按单位价值排序随后贪心遍历背包装满即停止class Item: Item def __init__(self, w: int, v: int): self.w w # Item weight self.v v # Item value def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: Fractional knapsack: Greedy algorithm # Create item list with two attributes: weight, value items [Item(w, v) for w, v in zip(wgt, val)] # Sort by unit value item.v / item.w from high to low items.sort(keylambda item: item.v / item.w, reverseTrue) # Loop for greedy selection res 0 for item in items: if item.w cap: # If remaining capacity is sufficient, put the entire current item into the knapsack res item.v cap - item.w else: # If remaining capacity is insufficient, put part of the current item into the knapsack res (item.v / item.w) * cap # No remaining capacity, so break out of the loop break return res复杂度内置排序通常耗时 $O(n \log n)$空间 $O(\log n)$ 或 $O(n)$视语言具体实现而定除排序外最坏情况需遍历整个物品列表贪心部分为 $O(n)$同时因初始化了Item对象列表空间复杂度为 $O(n)$。正确性证明反证法假设物品 $x$ 单位价值最高而某个算法得到了最优解res但该解中没有包含物品 $x$。现在从背包中任意物品上取下一单位重量替换为 $x$ 的一单位重量——由于 $x$ 单位价值最高替换后总价值必然大于res这与res是最优解矛盾因此任何最优解必然包含物品 $x$。对解中的其他物品也可构造同样的矛盾。结论是单位价值越高的物品永远是更优选择贪心策略有效。章节正文还给出了一个巧妙视角把物品重量与单位价值分别当作二维坐标图的横轴与纵轴分数背包问题可被理解为在横轴有界区间内寻找最大包围面积从几何角度再次印证了贪心策略的合理性。6. 典型案例二最大容量问题问题定义给定数组 $ht$每个元素代表一根竖直隔板的高度任意两根隔板连同它们之间的空间可构成一个容器。容器容量等于高度 × 宽度即面积其中高度由较矮的那根隔板决定宽度为两根隔板下标之差。请选出两根隔板使容量最大并返回该最大容量。任意两根隔板都能构成容器因此问题的状态是两根隔板的下标 $[i, j]$。设容量为 $cap[i, j]$则$$ cap[i, j] \min(ht[i], ht[j]) \times (j - i) $$若数组长度为 $n$选出两根隔板的方案数为 $C_n^2 \frac{n(n-1)}{2}$最直接的做法是穷举所有状态求最大容量时间复杂度 $O(n^2)$。贪心策略推导考虑状态 $[i, j]$$i j$ 且 $ht[i] ht[j]$即 $i$ 为短板、$j$ 为长板。此时把较高的隔板 $j$ 向内侧移动容量必然减小——宽度 $j-i$ 一定减小而高度由短板决定只可能不变或减小。反之只有向内侧移动较短板 $i$ 才可能使容量增加虽然宽度必然减小但高度可能上升移入的新隔板可能更高。由此得出贪心策略两个指针分别初始化在数组两端每轮移动对应较矮隔板的指针直到两指针相遇。每轮执行四步指针位于两端 → 计算当前容量 $cap[i, j]$ 并更新最大值 → 比较 $i$、$j$ 高度移动较矮者 → 重复直到相遇。仓库实现见 max_capacity.pydef max_capacity(ht: list[int]) - int: Max capacity: Greedy algorithm # Initialize i, j to be at both ends of the array i, j 0, len(ht) - 1 # Initial max capacity is 0 res 0 # Loop for greedy selection until the two boards meet while i j: # Update max capacity cap min(ht[i], ht[j]) * (j - i) res max(res, cap) # Move the shorter board inward if ht[i] ht[j]: i 1 else: j - 1 return res复杂度代码最多运行 $n$ 轮时间复杂度 $O(n)$变量 $i$、$j$、$res$ 仅使用常量额外空间空间复杂度 $O(1)$。正确性证明跳过状态论证贪心比穷举快的原因在于每轮贪心选择会跳过一些状态。例如在状态 $cap[i, j]$ 中 $i$ 是短板贪心把 $i$ 向内移动一位后下面这些状态将不再被检查$$ cap[i, i1], cap[i, i2], \dots, cap[i, j-2], cap[i, j-1] $$仔细观察会发现这些被跳过的状态恰好是移动长板 $j$ 向内所能到达的状态而前面已证明移动长板向内容量必然减小因此它们都不可能是最优解跳过它们不会漏掉最优值。可见移动短板是一种安全操作贪心策略正确。7. 典型案例三最大切分乘积问题问题定义给定正整数 $n$将其拆分为至少两个正整数之和求拆分所得各整数乘积的最大值。设 $n$ 被拆成 $m$ 个整数因子 $n_i$即 $n \sum_{i1}^{m}n_i$目标是最大化 $\max(\prod_{i1}^{m}n_i)$需要确定拆成多少份、每份取多少。两条贪心策略的推导策略一$\geq 4$ 的整数都应继续拆分。经验上两个整数之积常大于其和。从 $n$ 中拆出因子 $2$ 后乘积为 $2(n-2)$与 $n$ 比较$$ \begin{aligned} 2(n-2) \geq n \newline n \geq 4 \end{aligned} $$当 $n \geq 4$ 时拆出一个 $2$ 会增大乘积说明大于等于 4 的整数都应被拆分。因此最终拆分方案应只包含因子 $1$、$2$、$3$。策略二最优拆分因子是 $3$拆分中至多出现两个 $2$。在 $1$、$2$、$3$ 三者中 $1$ 最差$1 \times (n-1) n$ 恒成立拆出 1 反而使乘积减小。当 $n 6$ 时 $3 \times 3 2 \times 2 \times 2$说明拆 3 优于拆 2同时三个 $2$ 总能被替换为两个 $3$ 以得到更大乘积所以拆分方案中至多只能有两个 $2$。综上可归纳出最终策略输入整数 $n$不断拆出因子 $3$直到余数为 $0$、$1$ 或 $2$余数为 $0$$n$ 是 $3$ 的倍数无需处理余数为 $2$不再拆分原样保留余数为 $1$因 $2 \times 2 1 \times 3$把最后一个 $3$ 与余下的 $1$ 换成两个 $2$。代码实现无需用循环逐次拆分直接用整除得到 3 的个数 $a$、取模得到余数 $b$即 $n 3a b$。注意边界情形 $n \leq 3$必须拆出一个 $1$乘积为 $1 \times (n-1)$。仓库实现见 max_product_cutting.pydef max_product_cutting(n: int) - int: Max product cutting: Greedy algorithm # When n 3, must cut out a 1 if n 3: return 1 * (n - 1) # Greedily cut out 3, a is the number of 3s, b is the remainder a, b n // 3, n % 3 if b 1: # When the remainder is 1, convert a pair of 1 * 3 to 2 * 2 return int(math.pow(3, a - 1)) * 2 * 2 if b 2: # When the remainder is 2, do nothing return int(math.pow(3, a)) * 2 # When the remainder is 0, do nothing return int(math.pow(3, a))复杂度时间复杂度取决于语言中幂运算的实现方式。以 Python 为例运算符**与函数pow()复杂度为 $O(\log a)$而math.pow()内部调用 C 库的浮点pow()复杂度为 $O(1)$。变量 $a$、$b$ 仅使用常量额外空间因此空间复杂度为 $O(1)$。正确性证明反证法仅考虑 $n \geq 4$所有因子均 $\leq 3$若最优方案含因子 $x \geq 4$则可将其拆为 $2(x-2)$ 得到更大或不小于原值的乘积矛盾方案中不含 $1$若最优方案含因子 $1$可将其并入另一因子得到更大乘积矛盾方案中至多两个 $2$若最优方案含三个 $2$可替换为两个 $3$ 得到更大乘积矛盾。8. 核心要点速查表下表将本章小结的九条结论组织为便于复习与检索的对照表主题核心结论关键数据 / 佐证贪心原理每阶段做局部最优决策期望得到全局最优解定义见 greedy_algorithm.md迭代机制逐轮做贪心选择每轮把问题缩小为更小子问题零钱兑换每轮扣掉一枚最大可用硬币效率优势实现简单、效率高通常低于动态规划的时间复杂度零钱兑换贪心 $O(amt/\min(coins))$ vs 动态规划 $O(n \times amt)$零钱兑换某些硬币组合贪心保证最优某些组合结果很差正例[1,5,10,20,50,100]反例[1,20,50]、[1,49,50]适用条件贪心选择性质 最优子结构贪心选择性质体现策略有效性证明难度证明贪心选择性质困难证伪相对容易零钱兑换反例随手可得充分条件却难给出解题步骤问题分析 → 确定贪心策略 → 正确性证明确定策略为核心、正确性证明为主要难点分数背包允许选取物品一部分可用贪心求解按单位价值排序反证法证明正确最大容量穷举 $O(n^2)$移短板贪心优化到 $O(n)$被跳过状态均为移长板向内必不优最大切分乘积因子 $\geq 4$ 继续拆、最优因子为 3、至多两个 2复杂度取决于幂运算$O(1)$ 或 $O(\log n)$9. 在仓库中继续深入源码与运行方式本仓库为《Hello 算法》的多语言代码库贪心章节的完整代码以同名文件分布在每种语言的chapter_greedy/目录下。英文代码树位于en/codes/本文已核对的关键实现包括coin_change_greedy.py零钱兑换贪心含正例与两个反例的驱动测试数据fractional_knapsack.py分数背包Item类 按单位价值排序的贪心循环max_capacity.py最大容量双指针移动短板max_product_cutting.py最大切分乘积$a n // 3$、$b n % 3$ 的数学式计算。同一套算法在 Java、C、C、C#、JavaScript、TypeScript、Go、Swift、Rust、Kotlin、Ruby、Dart 等语言中均有对应实现例如 C 语言版本位于en/codes/c/chapter_greedy/含 coin_change_greedy.c、fractional_knapsack.c 等每份文件都带独立的驱动代码Driver Code可直接运行观察输入输出。例如在装有 Python 3 的环境中直接执行即可验证文中的贪心示例python en/codes/python/chapter_greedy/max_capacity.py python en/codes/python/chapter_greedy/coin_change_greedy.py若想对照书中配有逐步动画图解与推导过程的完整讲解可进一步阅读本章的正文页面greedy_algorithm.md、fractional_knapsack_problem.md、max_capacity_problem.md 与 max_product_cutting_problem.md配套的章节练习题位于 exercises.md。需要说明的是贪心并非万能——当问题不具备贪心选择性质时如一般化的零钱兑换、0-1 背包应转向动态规划等方案这正体现了《Hello 算法》以对比促理解的教学设计只有同时掌握贪心与动态规划各自的适用边界才能在真实问题中做出正确的算法选型。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Hello Algo 贪心算法章节总复习：贪心选择性质、三步解题框架与三大经典贪心问题的正确性证明
Hello Algo 贪心算法章节总复习贪心选择性质、三步解题框架与三大经典贪心问题的正确性证明【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文是对《Hello 算法》本仓库英文文档树en/docs/chapter_greedy/贪心算法章节章末总复习Summary的深度展开。它以官方小结的九条核心结论为主线把什么是贪心、贪心什么时候可靠、如何设计并证明贪心策略讲透并通过零钱兑换、分数背包、最大容量、最大切分乘积四个经典问题串起从策略推导到反证法证明的完整链路。读完你将掌握贪心算法与动态规划的本质区别、判断问题是否适用贪心的两大性质以及一套可复用的分析 → 定策略 → 证正确解题方法论。1. 章节总览这章在讲什么贪心算法Greedy Algorithm是求解最优化问题的常用方法其基本思路是在每个决策阶段选择当前看起来最好的选项即贪心地做出局部最优决策以期最终得到全局最优解。它实现简单、求解高效被广泛用于大量实际问题。本章小结summary.md把整章知识收敛为如下几条核心结论贪心算法通常用于求解最优化问题核心原理是在每个决策阶段做局部最优决策以期获得全局最优解贪心算法逐轮做贪心选择每轮把原问题转化为一个规模更小的子问题直到问题被解决贪心算法不仅实现简单求解效率也高相比动态规划通常拥有更低的时间复杂度在零钱兑换问题中某些硬币组合下贪心能保证最优解另一些组合下贪心可能得到很差的结果适合贪心求解的问题具备两大性质贪心选择性质与最优子结构其中贪心选择性质代表了贪心策略的有效性对复杂问题证明贪心选择性质并不简单相对而言证伪它更容易例如零钱兑换问题贪心解题主要有三步问题分析、确定贪心策略、正确性证明其中确定策略是核心正确性证明常是主要难点分数背包在 0-1 背包基础上允许选取物品的一部分因此可以用贪心求解其正确性可用反证法证明最大容量问题可用穷举法以 $O(n^2)$ 求解通过每轮向内侧移动较短板的贪心策略可优化到 $O(n)$最大切分乘积问题依次推导出两条贪心策略$\geq 4$ 的整数都应继续拆分、最优拆分因子是 $3$其时间复杂度取决于幂运算的实现方式通常为 $O(1)$ 或 $O(\log n)$。以上每一条都会在后续小节展开。对应章节正文分别位于 greedy_algorithm.md贪心算法总论、fractional_knapsack_problem.md分数背包问题、max_capacity_problem.md最大容量问题、max_product_cutting_problem.md最大切分乘积问题。2. 贪心算法是什么与动态规划的分野贪心算法与动态规划都常用于求解最优化问题两者都依赖最优子结构性质但工作方式截然不同动态规划在做出当前决策时会考虑之前的所有决策用过去子问题的解来构造当前子问题的解贪心算法不考虑过去的决策而是向前做出贪心选择不断缩小问题规模直到问题被解决。为了直观理解贪心的工作方式章节正文以零钱兑换问题切入该问题在完全背包章节中已做过介绍。贪心策略为每次选择不超过目标金额、且最接近目标金额的那枚硬币重复此步骤直到凑齐目标金额。仓库实现见 coin_change_greedy.pydef coin_change_greedy(coins: list[int], amt: int) - int: Coin change: Greedy algorithm # Assume coins list is sorted i len(coins) - 1 count 0 # Loop to make greedy choices until no remaining amount while amt 0: # Find the coin that is less than and closest to the remaining amount while i 0 and coins[i] amt: i - 1 # Choose coins[i] amt - coins[i] count 1 # If no feasible solution is found, return -1 return count if amt 0 else -1贪心优势简单高效。若硬币最小面额为 $\min(coins)$贪心选择的循环最多执行 $amt / \min(coins)$ 次时间复杂度约为 $O(amt / \min(coins))$远低于动态规划解法的 $O(n \times amt)$。贪心局限某些硬币组合下无法得到最优解。下图展示了两个反例正例 $coins [1, 5, 10, 20, 50, 100]$该硬币组合下贪心对任意 $amt$ 都能找到最优解反例 $coins [1, 20, 50]$设 $amt 60$贪心只能找到 $50 1 \times 10$共 11 枚而动态规划能找到 $20 20 20$仅 3 枚反例 $coins [1, 49, 50]$设 $amt 98$贪心只能找到 $50 1 \times 48$共 49 枚而动态规划能找到 $49 49$仅 2 枚。以上反例在 coin_change_greedy.py 的驱动代码中均有对应测试数据。因此对零钱兑换这类问题贪心无法保证全局最优甚至可能产生很差的结果更适合用动态规划求解。总体而言贪心算法适用于两类场景能保证最优解此时贪心往往是最佳选择因为其效率通常优于回溯和动态规划能找到近似最优解对很多复杂问题求全局最优非常困难能高效求得次优解已是很好的结果。3. 适用条件贪心选择性质与最优子结构什么样的问题适合贪心相较动态规划贪心算法的适用条件更严格主要考察两大性质贪心选择性质只有当局部最优选择总能导向全局最优解时贪心才能保证得到最优解最优子结构原问题的最优解包含子问题的最优解该性质在动态规划章节已详细介绍此处不再展开。其中贪心选择性质是判断核心它直接代表了贪心策略的有效性。然而实践中证明它并不容易。在零钱兑换问题中虽然很容易举出反例来证伪贪心选择性质但要证明某组硬币在什么条件下贪心恒成立却困难得多——通常只能凭直觉或举例给出模糊答案难以给出严谨数学证明。章节正文提到学界有一篇论文给出了判定硬币集合对任意金额是否可被贪心最优求解的 $O(n^3)$ 算法Pearson, D.,A polynomial-time algorithm for the change-making problem, Operations Research Letters, 2005。4. 贪心解题三步框架贪心问题的一般求解过程可归纳为三步问题分析梳理并理解问题特征包括状态定义、优化目标和约束条件这一步骤同样出现在回溯与动态规划中确定贪心策略决定每一步如何做贪心选择策略应让问题规模逐步缩小最终解决整个问题正确性证明通常需要证明问题同时具备贪心选择性质与最优子结构可能要借助数学归纳法或反证法。其中确定贪心策略是核心步骤实践中却并不容易原因主要有二策略因问题而异很多问题的贪心策略相当直观可凭粗略推理与试验得出但对复杂问题策略可能隐藏很深十分考验解题经验与算法功底部分策略极具欺骗性我们可能信心满满地设计策略、写出代码并提交却仍有测试用例失败——因为该策略只是部分正确零钱兑换就是典型例子。为了保证正确性应对贪心策略做严格数学证明通常采用反证法或数学归纳法若证明暂无头绪也可退一步通过针对测试用例的调试来逐步修正、验证贪心策略。章节正文还给出了典型的贪心适用问题清单区间调度总是选最早结束的任务、分数背包总是选单位价值最高的物品、股票交易多次交易、先卖后买、利润最大化、哈夫曼编码每次合并频率最低的两个节点得到最小带权路径长度、Dijkstra 算法非负权图单源最短路径等。5. 典型案例一分数背包问题问题定义给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$背包容量为 $cap$。每个物品只能选一次但可以选取其一部分价值与选取重量成正比求容量约束下能装入背包的最大总价值。分数背包与 0-1 背包整体结构非常相似状态同样包含当前物品 $i$ 与容量 $c$关键区别在于允许按比例切割物品物品 $i$ 的单位重量价值为 $val[i-1] / wgt[i-1]$称为单位价值若装入物品 $i$ 中重量为 $w$ 的部分则背包获得的价值为 $w \times val[i-1] / wgt[i-1]$。贪心策略最大化总价值本质上是优先放入单位价值更高的物品。由此得出三步策略——按单位价值从高到低排序逐轮贪心选择当前单位价值最高的物品若剩余容量不足则取当前物品的一部分装满背包。仓库实现见 fractional_knapsack.py。代码定义了一个Item类以便按单位价值排序随后贪心遍历背包装满即停止class Item: Item def __init__(self, w: int, v: int): self.w w # Item weight self.v v # Item value def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: Fractional knapsack: Greedy algorithm # Create item list with two attributes: weight, value items [Item(w, v) for w, v in zip(wgt, val)] # Sort by unit value item.v / item.w from high to low items.sort(keylambda item: item.v / item.w, reverseTrue) # Loop for greedy selection res 0 for item in items: if item.w cap: # If remaining capacity is sufficient, put the entire current item into the knapsack res item.v cap - item.w else: # If remaining capacity is insufficient, put part of the current item into the knapsack res (item.v / item.w) * cap # No remaining capacity, so break out of the loop break return res复杂度内置排序通常耗时 $O(n \log n)$空间 $O(\log n)$ 或 $O(n)$视语言具体实现而定除排序外最坏情况需遍历整个物品列表贪心部分为 $O(n)$同时因初始化了Item对象列表空间复杂度为 $O(n)$。正确性证明反证法假设物品 $x$ 单位价值最高而某个算法得到了最优解res但该解中没有包含物品 $x$。现在从背包中任意物品上取下一单位重量替换为 $x$ 的一单位重量——由于 $x$ 单位价值最高替换后总价值必然大于res这与res是最优解矛盾因此任何最优解必然包含物品 $x$。对解中的其他物品也可构造同样的矛盾。结论是单位价值越高的物品永远是更优选择贪心策略有效。章节正文还给出了一个巧妙视角把物品重量与单位价值分别当作二维坐标图的横轴与纵轴分数背包问题可被理解为在横轴有界区间内寻找最大包围面积从几何角度再次印证了贪心策略的合理性。6. 典型案例二最大容量问题问题定义给定数组 $ht$每个元素代表一根竖直隔板的高度任意两根隔板连同它们之间的空间可构成一个容器。容器容量等于高度 × 宽度即面积其中高度由较矮的那根隔板决定宽度为两根隔板下标之差。请选出两根隔板使容量最大并返回该最大容量。任意两根隔板都能构成容器因此问题的状态是两根隔板的下标 $[i, j]$。设容量为 $cap[i, j]$则$$ cap[i, j] \min(ht[i], ht[j]) \times (j - i) $$若数组长度为 $n$选出两根隔板的方案数为 $C_n^2 \frac{n(n-1)}{2}$最直接的做法是穷举所有状态求最大容量时间复杂度 $O(n^2)$。贪心策略推导考虑状态 $[i, j]$$i j$ 且 $ht[i] ht[j]$即 $i$ 为短板、$j$ 为长板。此时把较高的隔板 $j$ 向内侧移动容量必然减小——宽度 $j-i$ 一定减小而高度由短板决定只可能不变或减小。反之只有向内侧移动较短板 $i$ 才可能使容量增加虽然宽度必然减小但高度可能上升移入的新隔板可能更高。由此得出贪心策略两个指针分别初始化在数组两端每轮移动对应较矮隔板的指针直到两指针相遇。每轮执行四步指针位于两端 → 计算当前容量 $cap[i, j]$ 并更新最大值 → 比较 $i$、$j$ 高度移动较矮者 → 重复直到相遇。仓库实现见 max_capacity.pydef max_capacity(ht: list[int]) - int: Max capacity: Greedy algorithm # Initialize i, j to be at both ends of the array i, j 0, len(ht) - 1 # Initial max capacity is 0 res 0 # Loop for greedy selection until the two boards meet while i j: # Update max capacity cap min(ht[i], ht[j]) * (j - i) res max(res, cap) # Move the shorter board inward if ht[i] ht[j]: i 1 else: j - 1 return res复杂度代码最多运行 $n$ 轮时间复杂度 $O(n)$变量 $i$、$j$、$res$ 仅使用常量额外空间空间复杂度 $O(1)$。正确性证明跳过状态论证贪心比穷举快的原因在于每轮贪心选择会跳过一些状态。例如在状态 $cap[i, j]$ 中 $i$ 是短板贪心把 $i$ 向内移动一位后下面这些状态将不再被检查$$ cap[i, i1], cap[i, i2], \dots, cap[i, j-2], cap[i, j-1] $$仔细观察会发现这些被跳过的状态恰好是移动长板 $j$ 向内所能到达的状态而前面已证明移动长板向内容量必然减小因此它们都不可能是最优解跳过它们不会漏掉最优值。可见移动短板是一种安全操作贪心策略正确。7. 典型案例三最大切分乘积问题问题定义给定正整数 $n$将其拆分为至少两个正整数之和求拆分所得各整数乘积的最大值。设 $n$ 被拆成 $m$ 个整数因子 $n_i$即 $n \sum_{i1}^{m}n_i$目标是最大化 $\max(\prod_{i1}^{m}n_i)$需要确定拆成多少份、每份取多少。两条贪心策略的推导策略一$\geq 4$ 的整数都应继续拆分。经验上两个整数之积常大于其和。从 $n$ 中拆出因子 $2$ 后乘积为 $2(n-2)$与 $n$ 比较$$ \begin{aligned} 2(n-2) \geq n \newline n \geq 4 \end{aligned} $$当 $n \geq 4$ 时拆出一个 $2$ 会增大乘积说明大于等于 4 的整数都应被拆分。因此最终拆分方案应只包含因子 $1$、$2$、$3$。策略二最优拆分因子是 $3$拆分中至多出现两个 $2$。在 $1$、$2$、$3$ 三者中 $1$ 最差$1 \times (n-1) n$ 恒成立拆出 1 反而使乘积减小。当 $n 6$ 时 $3 \times 3 2 \times 2 \times 2$说明拆 3 优于拆 2同时三个 $2$ 总能被替换为两个 $3$ 以得到更大乘积所以拆分方案中至多只能有两个 $2$。综上可归纳出最终策略输入整数 $n$不断拆出因子 $3$直到余数为 $0$、$1$ 或 $2$余数为 $0$$n$ 是 $3$ 的倍数无需处理余数为 $2$不再拆分原样保留余数为 $1$因 $2 \times 2 1 \times 3$把最后一个 $3$ 与余下的 $1$ 换成两个 $2$。代码实现无需用循环逐次拆分直接用整除得到 3 的个数 $a$、取模得到余数 $b$即 $n 3a b$。注意边界情形 $n \leq 3$必须拆出一个 $1$乘积为 $1 \times (n-1)$。仓库实现见 max_product_cutting.pydef max_product_cutting(n: int) - int: Max product cutting: Greedy algorithm # When n 3, must cut out a 1 if n 3: return 1 * (n - 1) # Greedily cut out 3, a is the number of 3s, b is the remainder a, b n // 3, n % 3 if b 1: # When the remainder is 1, convert a pair of 1 * 3 to 2 * 2 return int(math.pow(3, a - 1)) * 2 * 2 if b 2: # When the remainder is 2, do nothing return int(math.pow(3, a)) * 2 # When the remainder is 0, do nothing return int(math.pow(3, a))复杂度时间复杂度取决于语言中幂运算的实现方式。以 Python 为例运算符**与函数pow()复杂度为 $O(\log a)$而math.pow()内部调用 C 库的浮点pow()复杂度为 $O(1)$。变量 $a$、$b$ 仅使用常量额外空间因此空间复杂度为 $O(1)$。正确性证明反证法仅考虑 $n \geq 4$所有因子均 $\leq 3$若最优方案含因子 $x \geq 4$则可将其拆为 $2(x-2)$ 得到更大或不小于原值的乘积矛盾方案中不含 $1$若最优方案含因子 $1$可将其并入另一因子得到更大乘积矛盾方案中至多两个 $2$若最优方案含三个 $2$可替换为两个 $3$ 得到更大乘积矛盾。8. 核心要点速查表下表将本章小结的九条结论组织为便于复习与检索的对照表主题核心结论关键数据 / 佐证贪心原理每阶段做局部最优决策期望得到全局最优解定义见 greedy_algorithm.md迭代机制逐轮做贪心选择每轮把问题缩小为更小子问题零钱兑换每轮扣掉一枚最大可用硬币效率优势实现简单、效率高通常低于动态规划的时间复杂度零钱兑换贪心 $O(amt/\min(coins))$ vs 动态规划 $O(n \times amt)$零钱兑换某些硬币组合贪心保证最优某些组合结果很差正例[1,5,10,20,50,100]反例[1,20,50]、[1,49,50]适用条件贪心选择性质 最优子结构贪心选择性质体现策略有效性证明难度证明贪心选择性质困难证伪相对容易零钱兑换反例随手可得充分条件却难给出解题步骤问题分析 → 确定贪心策略 → 正确性证明确定策略为核心、正确性证明为主要难点分数背包允许选取物品一部分可用贪心求解按单位价值排序反证法证明正确最大容量穷举 $O(n^2)$移短板贪心优化到 $O(n)$被跳过状态均为移长板向内必不优最大切分乘积因子 $\geq 4$ 继续拆、最优因子为 3、至多两个 2复杂度取决于幂运算$O(1)$ 或 $O(\log n)$9. 在仓库中继续深入源码与运行方式本仓库为《Hello 算法》的多语言代码库贪心章节的完整代码以同名文件分布在每种语言的chapter_greedy/目录下。英文代码树位于en/codes/本文已核对的关键实现包括coin_change_greedy.py零钱兑换贪心含正例与两个反例的驱动测试数据fractional_knapsack.py分数背包Item类 按单位价值排序的贪心循环max_capacity.py最大容量双指针移动短板max_product_cutting.py最大切分乘积$a n // 3$、$b n % 3$ 的数学式计算。同一套算法在 Java、C、C、C#、JavaScript、TypeScript、Go、Swift、Rust、Kotlin、Ruby、Dart 等语言中均有对应实现例如 C 语言版本位于en/codes/c/chapter_greedy/含 coin_change_greedy.c、fractional_knapsack.c 等每份文件都带独立的驱动代码Driver Code可直接运行观察输入输出。例如在装有 Python 3 的环境中直接执行即可验证文中的贪心示例python en/codes/python/chapter_greedy/max_capacity.py python en/codes/python/chapter_greedy/coin_change_greedy.py若想对照书中配有逐步动画图解与推导过程的完整讲解可进一步阅读本章的正文页面greedy_algorithm.md、fractional_knapsack_problem.md、max_capacity_problem.md 与 max_product_cutting_problem.md配套的章节练习题位于 exercises.md。需要说明的是贪心并非万能——当问题不具备贪心选择性质时如一般化的零钱兑换、0-1 背包应转向动态规划等方案这正体现了《Hello 算法》以对比促理解的教学设计只有同时掌握贪心与动态规划各自的适用边界才能在真实问题中做出正确的算法选型。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考