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\le 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. 核心要点速查表

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

主题	核心结论	关键数据 / 佐证
贪心原理	每阶段做局部最优决策，期望得到全局最优解	定义见 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 算法》以对比促理解的教学设计：只有同时掌握贪心与动态规划各自的适用边界，才能在真实问题中做出正确的算法选型。