Hello 算法 · 贪心算法实战：零钱兑换（Coin Change）问题的贪心求解与可视化运行解析

导读

本文聚焦《Hello 算法》贪心算法章节中的经典例题「零钱兑换」（コイン交換 / Coin Change），以仓库内 Python 可视化运行文档 及其背后的 Python 源码为主线，完整拆解贪心策略的代码实现、执行轨迹、正例与反例，并给出复杂度分析与仓库内多语言实现入口。读完本文，你将能独立读懂并运行该算法，理解"局部最优叠加为何不等于全局最优"，以及为什么某些硬币面值组合下需要改用动态规划。

一、这道例题"长"在仓库的哪里

在《Hello 算法》仓库中，每个章节的示例代码通常对应三份形态：

• 章节正文：位于 docs/chapter_greedy/greedy_algorithm.md（日文版见 ja/docs/chapter_greedy/greedy_algorithm.md），正文通过 [file]{coin_change_greedy}-[class]{}-[func]{coin_change_greedy} 锚点引入源码；
• 可执行源码：如 Python 版实现，以及各语言的同名文件；
• 可视化运行页：即 coin_change_greedy.md，它把 Python 代码逐语句编码进链接参数，用于在代码可视化工具中单步观察变量与执行流（仓库中另有英文、简体中文、繁体中文、俄文等多套对应目录，结构一致）。

本文关联的 可视化运行文档 内容主体是 coin_change_greedy() 函数及其两组测试输入——一组能证明贪心可得到最优解，另一组专门证明贪心会失效——这正是下文逐行讲解的对象。

二、问题定义与贪心策略

问题描述：给定 $n$ 种硬币，第 $i$ 种硬币面值为 coins[i-1]，目标金额为 amt，每种硬币可以重复选取，问凑出目标金额所需的最少硬币数量；若无法凑出，则返回 -1。

贪心策略非常直观：

每次都选择"面值不大于当前剩余金额、且尽可能接近它"的硬币，不断重复，直到剩余金额归零。

下图展示了该策略的决策路径（以目标金额 131 为例）：依次选择 100、20、10、1，剩余金额从 131 → 31 → 11 → 1 → 0，恰好 4 枚硬币凑齐。

三、核心代码实现与执行轨迹

以下代码摘自 Python 源码（日文注释版本见 ja/codes/python/chapter_greedy/coin_change_greedy.py），与可视化运行页中的函数完全一致：

def coin_change_greedy(coins: list[int], amt: int) -> int:
    """零钱兑换：贪心"""
    # 假设 coins 列表有序
    i = len(coins) - 1
    count = 0
    # 循环进行贪心选择，直到无剩余金额
    while amt > 0:
        # 找到小于且最接近剩余金额的硬币
        while i > 0 and coins[i] > amt:
            i -= 1
        # 选择 coins[i]
        amt -= coins[i]
        count += 1
    # 若未找到可行方案，则返回 -1
    return count if amt == 0 else -1

实现要点如下：

1. 前提假设：coins 列表必须是升序有序的，函数从最大面值 coins[len(coins)-1] 开始尝试；
2. 双循环结构：外层 while amt > 0 控制"剩余金额未归零则继续"，内层 while i > 0 and coins[i] > amt 让指针 i 向左移动，找到第一个面值不超过剩余金额的硬币；
3. 指针只减不增：由于剩余金额 amt 单调递减，指针 i 只会向左回退、不会右移，整个过程中所有内层移动累计不超过 $n$ 次，算法实现非常轻量；
4. 失败返回 -1：若某种硬币组合无法整除剩余金额，循环结束时 amt != 0，函数返回 -1。

手动推演：amt = 186

以可视化页第一组输入 coins = [1, 5, 10, 20, 50, 100]、amt = 186 为例，逐步执行如下：

轮次	当前剩余金额	贪心选择的硬币	选择后剩余
1	186	100	86
2	86	50	36
3	36	20	16
4	16	10	6
5	6	5	1
6	1	1	0

最终得到组合 100 + 50 + 20 + 10 + 5 + 1 = 186，共 6 枚，这正是该硬币组合下的最优解。

四、贪心不是万能的：两组经典反例

并不是任何面值组合下，贪心都能给出最优解。下面的反例恰好证明了"每一步局部最优，最终却错失全局最优"。

第一组反例（同样内置于可视化运行页与源码中）：

# 贪心：无法保证得到全局最优解
coins = [1, 20, 50]
amt = 60

• 贪心过程：先选面值最大的 50，剩余 10；此后只能反复选 1，共 50 + 1×10 = 60，需要 11 枚；
• 真正的最优解：20 + 20 + 20 = 60，只需 3 枚。

原因在于：选中 50 虽然"当前最划算"，却把剩余金额 60 − 50 = 10 逼进了只能用小面值硬币填补的"死角"，反而抬高了总枚数。

第二组反例来自 章节正文 及源码中的附加测试：

coins = [1, 49, 50]
amt = 98

• 贪心过程：先选 50，剩余 48，只能补 48 枚 1 元，共 50 + 1×48 = 98，需要 49 枚；
• 真正的最优解：49 + 49 = 98，只需 2 枚。

下图直观对比了这两组反例中贪心（局部最优）与动态规划（全局最优）的差距：

由此可以得出一个重要结论：面对零钱兑换问题，贪心算法无法保证全局最优，甚至可能给出极差的解；在仓库中，该问题更适合用动态规划章节的完全背包思路求解，这也是书中"贪心法存在局限性"这一节的核心论据。

五、效率分析：贪心为什么"快"

设最小硬币面值为 $\min(coins)$：

• 贪心外层循环每轮至少消耗 $\min(coins)$ 金额，故循环次数至多为 $amt / \min(coins)$；加上指针总移动不超过 $n$ 次，整体时间复杂度约为 $O(amt/\min(coins))$，空间复杂度 $O(1)$；
• 相比之下，书中动态规划解零钱兑换的时间复杂度为 $O(n \times amt)$。

也就是说，在硬币组合满足贪心性质的前提下，贪心往往比动态规划少一个数量级的工作量。但这种"快"是有前提的，即问题必须满足：

1. 贪心选择性质：每一步的局部最优选择始终能导向全局最优解；
2. 最优子结构：原问题的最优解包含子问题的最优解。

零钱兑换问题恰恰是"易于证伪、难以证实"的代表——书中引用了 Pearson 发表于 Operations Research Letters（2005）的论文：存在 $O(n^3)$ 时间的算法来判断某个硬币组合是否能让贪心对任意金额都得到最优解。这提醒我们：设计贪心策略后，仍应通过反证法或数学归纳法做正确性验证。

六、运行与验证：一键运行与可视化

如果你想亲自观察执行过程，有两种途径：

方式一：本地直接运行 Python 源码

python3 codes/python/chapter_greedy/coin_change_greedy.py

该脚本输出三组测试结果（对应正例与两组反例），终端将依次打印所需最少硬币枚数；代码依赖 list[int] 类型标注，建议使用 Python 3.9+（可视化页默认 Python 3.11）。

方式二：打开可视化运行页逐步观察

打开 可视化运行文档，其中的链接会把源码加载到支持单步执行的代码可视化工具中，可逐行观察 amt、i、count 三个变量的实时变化，以及剩余金额的递减过程，非常适合理解第 15–20 行"指针回退 → 选取硬币"的循环节奏。日文版对应文件见 ja/codes/pythontutor/chapter_greedy/coin_change_greedy.md。

七、仓库中的多语言实现与测试

同一函数在仓库中提供了多语言实现，路径规则均为 <语言目录>/chapter_greedy/coin_change_greedy.<扩展名>，例如：

• Python：codes/python/chapter_greedy/coin_change_greedy.py
• Java：codes/java/chapter_greedy/coin_change_greedy.java
• C++：codes/cpp/chapter_greedy/coin_change_greedy.cpp
• Go：codes/go/chapter_greedy/coin_change_greedy.go，并配有单元测试 coin_change_greedy_test.go
• Rust / C / C# / JavaScript / TypeScript / Swift / Kotlin / Ruby / Dart 等版本位于 codes/ 下对应语言目录

英文（en/codes）、日文（ja/codes）、繁体中文（zh-hant/codes）、俄文（ru/codes）目录均保持相同的文件布局，便于对照阅读与二次验证。若想深究其正确性，可在 Go 目录下运行对应测试：

cd codes/go && go test ./chapter_greedy/

小结

本文以 coin_change_greedy.md 对应的零钱兑换贪心代码为线索，串联了策略描述、代码拆解、手算推演、反例论证与复杂度分析：贪心在 [1,5,10,20,50,100] 这类"亲贪心"面值组合下高效且正确，但在 [1,20,50] 与 [1,49,50] 组合下会严重偏离最优解。理解这一"局部最优 ≠ 全局最优"的边界，正是后续学习贪心选择性质与动态规划完整背包解法的关键起点。