编辑“︁贪心算法中的反例分析”︁（章节）

== 经典反例：硬币找零问题 ==

=== 问题描述 ===
给定一个硬币面额的集合和一个目标金额，要求用最少数量的硬币凑出目标金额。假设硬币面额是无限的。

=== 贪心策略 ===
每次选择面额最大的硬币，直到凑出目标金额。

=== 反例分析 ===
考虑硬币面额为 {1, 3, 4}，目标金额为 6。

* '''贪心策略的步骤'''：
  # 选择 4，剩余金额为 2。
  # 选择 1，剩余金额为 1。
  # 选择 1，剩余金额为 0。
  # 总共使用 3 枚硬币（4, 1, 1）。

* '''最优解'''：
  # 选择 3，剩余金额为 3。
  # 选择 3，剩余金额为 0。
  # 总共使用 2 枚硬币（3, 3）。

贪心策略在这个例子中得到了次优解，因为它过早地选择了面额较大的硬币（4），导致后续需要更多的硬币来凑出剩余金额。

=== 代码示例 ===
以下是一个贪心算法的实现及其在反例中的表现：

<syntaxhighlight lang="python">
def greedy_coin_change(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

# 反例测试
coins = [1, 3, 4]
amount = 6
print(greedy_coin_change(coins, amount))  # 输出：3（次优解）
</syntaxhighlight>