企业官网建设流程全解析

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.py：

def 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 的驱动代码中均有对应测试数据。因此：对零钱兑换这类问题，贪心无法保证全局最优，甚至可能产生很差的结果，更适合用动态规划求解。

总体而言，贪心算法适用于两类场景：

1. 能保证最优解：此时贪心往往是最佳选择，因为其效率通常优于回溯和动态规划；
2. 能找到近似最优解：对很多复杂问题，求全局最优非常困难，能高效求得次优解已是很好的结果。

3. 适用条件：贪心选择性质与最优子结构

什么样的问题适合贪心？相较动态规划，贪心算法的适用条件更严格，主要考察两大性质：

• 贪心选择性质：只有当局部最优选择总能导向全局最优解时，贪心才能保证得到最优解；
• 最优子结构：原问题的最优解包含子问题的最优解（该性质在"动态规划"章节已详细介绍，此处不再展开）。

其中贪心选择性质是判断核心，它直接代表了贪心策略的有效性。然而实践中证明它并不容易。在零钱兑换问题中，虽然很容易举出反例来证伪贪心选择性质，但要证明"某组硬币在什么条件下贪心恒成立"却困难得多——通常只能凭直觉或举例给出模糊答案，难以给出严谨数学证明。章节正文提到，学界有一篇论文给出了判定"硬币集合对任意金额是否可被贪心最优求解"的 $O(n^3)$ 算法（Pearson, D.,A polynomial-time algorithm for the change-making problem, Operations Research Letters, 2005）。

4. 贪心解题三步框架

贪心问题的一般求解过程可归纳为三步：

1. 问题分析：梳理并理解问题特征，包括状态定义、优化目标和约束条件（这一步骤同样出现在回溯与动态规划中）；
2. 确定贪心策略：决定每一步如何做贪心选择，策略应让问题规模逐步缩小，最终解决整个问题；
3. 正确性证明：通常需要证明问题同时具备贪心选择性质与最优子结构，可能要借助数学归纳法或反证法。

其中确定贪心策略是核心步骤，实践中却并不容易，原因主要有二：

• 策略因问题而异：很多问题的贪心策略相当直观，可凭粗略推理与试验得出；但对复杂问题，策略可能隐藏很深，十分考验解题经验与算法功底；
• 部分策略极具欺骗性：我们可能信心满满地设计策略、写出代码并提交，却仍有测试用例失败——因为该策略只是"部分正确"，零钱兑换就是典型例子。

为了保证正确性，应对贪心策略做严格数学证明，通常采用反证法或数学归纳法；若证明暂无头绪，也可退一步，通过针对测试用例的调试来逐步修正、验证贪心策略。

章节正文还给出了典型的贪心适用问题清单：区间调度（总是选最早结束的任务）、分数背包（总是选单位价值最高的物品）、股票交易（多次交易、先卖后买、利润最大化）、哈夫曼编码（每次合并频率最低的两个节点，得到最小带权路径长度）、Dijkstra 算法（非负权图单源最短路径）等。

5. 典型案例一：分数背包问题

问题定义：给定 $n$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$，背包容量为 $cap$。每个物品只能选一次，但可以选取其一部分，价值与选取重量成正比，求容量约束下能装入背包的最大总价值。

分数背包与 0-1 背包整体结构非常相似（状态同样包含当前物品 $i$ 与容量 $c$），关键区别在于允许按比例切割物品：

1. 物品 $i$ 的单位重量价值为 $val[i-1] / wgt[i-1]$，称为"单位价值"；
2. 若装入物品 $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(key=lambda item: item.v / item.w, reverse=True) # 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.py：

def 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, i+1], cap[i, i+2], \dots, cap[i, j-2], cap[i, j-1] $$

仔细观察会发现，这些被跳过的状态恰好是"移动长板 $j$ 向内"所能到达的状态，而前面已证明移动长板向内容量必然减小，因此它们都不可能是最优解，跳过它们不会漏掉最优值。可见移动短板是一种"安全"操作，贪心策略正确。

7. 典型案例三：最大切分乘积问题

问题定义：给定正整数 $n$，将其拆分为至少两个正整数之和，求拆分所得各整数乘积的最大值。设 $n$ 被拆成 $m$ 个整数因子 $n_i$，即 $n = \sum_{i=1}^{m}n_i$，目标是最大化 $\max(\prod_{i=1}^{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$。

综上可归纳出最终策略：

1. 输入整数 $n$，不断拆出因子 $3$，直到余数为 $0$、$1$ 或 $2$；
2. 余数为 $0$：$n$ 是 $3$ 的倍数，无需处理；
3. 余数为 $2$：不再拆分，原样保留；
4. 余数为 $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.py：

def 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$）：

1. 所有因子均 $\leq 3$：若最优方案含因子 $x \geq 4$，则可将其拆为 $2(x-2)$ 得到更大（或不小于原值）的乘积，矛盾；
2. 方案中不含 $1$：若最优方案含因子 $1$，可将其并入另一因子得到更大乘积，矛盾；
3. 方案中至多两个 $2$：若最优方案含三个 $2$，可替换为两个 $3$ 得到更大乘积，矛盾。

8. 核心要点速查表

下表将本章小结的九条结论组织为便于复习与检索的对照表：

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