数据结构与算法 / 系统课时

识别贪心反例

识别贪心反例

很多贪心规则听起来很自然,但“每一步看起来最好”并不等于最终答案最优。本课通过硬币找零反例,建立一套可复用的检验方法:缩小规模、执行规则、计算最优解并比较差异。

学习目标

  • 能把口头描述的贪心策略写成明确、可执行的选择规则。
  • 能构造小规模输入,并用最优解对照判断贪心规则是否失效。
  • 能解释一个反例为什么足以否定“对所有输入都正确”的结论。

反例为什么有效

贪心算法通常声称:对任意合法输入,每一步都选择当前最优项,最终仍能得到全局最优解。这是一个全称命题。要否定它,不需要枚举全部输入,只需找到一个合法输入,使贪心结果严格差于最优结果。

以硬币集合 1、3、4 和目标金额 6 为例,“每次选不超过剩余金额的最大硬币”会得到 4 + 1 + 1,共 3 枚;最优方案是 3 + 3,只需 2 枚。因此,该规则并不适用于所有硬币系统。

贪心找零与最优找零的反例对比

构造小规模反例

可以按以下顺序检验一个看似合理的贪心规则:

  1. 明确规则。写清楚每一步比较什么、选择什么,以及相等时如何处理。
  2. 缩小输入。优先尝试 3~6 个元素、较小权值或较短区间,便于手算全部候选。
  3. 保留“诱饵”。让局部最优项看起来很有吸引力,但选择它后会破坏后续组合。
  4. 计算最优解。可用穷举、动态规划或可靠的基准算法得到对照答案。
  5. 比较目标值。只要贪心结果更差,就得到有效反例;若暂未发现,只能说明测试未命中,不能证明算法正确。

对找零问题,设目标金额为 AA、硬币种类数为 nn。动态规划求最少硬币数的时间复杂度为 O(nA)O(nA),足以作为小规模反例搜索的基准。

完整可运行示例

下面的 Python 程序同时运行贪心找零和动态规划找零,并比较两者的硬币数量。

python
from math import inf

def greedy_change(coins, amount):
    result = []
    remaining = amount

    # 贪心规则:每次选择不超过剩余金额的最大硬币
    for coin in sorted(coins, reverse=True):
        while coin <= remaining:
            result.append(coin)
            remaining -= coin

    return result if remaining == 0 else None

def optimal_change(coins, amount):
    dp = [0] + [inf] * amount
    previous_coin = [-1] * (amount + 1)

    # 动态规划给出小规模输入的可靠最优答案
    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current and dp[current - coin] + 1 < dp[current]:
                dp[current] = dp[current - coin] + 1
                previous_coin[current] = coin

    if dp[amount] == inf:
        return None

    result = []
    current = amount
    while current > 0:
        coin = previous_coin[current]
        result.append(coin)
        current -= coin

    return result

def main():
    coins = [1, 3, 4]
    amount = 6

    greedy_result = greedy_change(coins, amount)
    optimal_result = optimal_change(coins, amount)

    print(f"硬币集合: {coins}")
    print(f"目标金额: {amount}")
    print(f"贪心结果: {greedy_result},硬币数 = {len(greedy_result)}")
    print(f"最优结果: {optimal_result},硬币数 = {len(optimal_result)}")

    if len(greedy_result) > len(optimal_result):
        print("发现反例: 贪心规则并非始终最优")
    else:
        print("当前输入未发现反例")

if __name__ == "__main__":
    main()

运行命令如下:

bash
python greedy_counterexample.py

预期输出

text
硬币集合: [1, 3, 4]
目标金额: 6
贪心结果: [4, 1, 1],硬币数 = 3
最优结果: [3, 3],硬币数 = 2
发现反例: 贪心规则并非始终最优

常见错误与练习

常见误区是把“很多样例都通过”当成正确性证明。测试只能发现错误,不能覆盖无限输入;真正的正确性仍需贪心选择性质和最优子结构等证明。另一个误区是只比较方案外观,而没有比较题目要求的目标值,例如总成本、数量或完成时间。

练习 1:检验硬币集合 1、5、10、25 在目标金额 1~100 内是否出现反例。要求复用示例程序自动比较,并记录搜索范围与结论。

练习 2:为“总是选择价值最高的物品”这一 0-1 背包规则构造一个不超过 4 件物品的反例。验收条件是给出容量、每件物品的重量与价值,并证明贪心总价值小于最优总价值。

本课总结

  • 一个合法反例即可否定“贪心规则对所有输入都最优”的全称结论。
  • 高效构造反例的关键是缩小规模、设计局部诱饵,并用可靠算法计算最优答案。
  • 未找到反例不等于已经证明正确,正确性仍需严格论证。

下一课预告

下一阶段将继续学习如何从反例检验走向正确性证明,理解哪些结构条件能够保证局部选择安全地导向全局最优。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

识别贪心反例

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通