数据结构与算法 / 系统课时
识别贪心反例
识别贪心反例
很多贪心规则听起来很自然,但“每一步看起来最好”并不等于最终答案最优。本课通过硬币找零反例,建立一套可复用的检验方法:缩小规模、执行规则、计算最优解并比较差异。
学习目标
- 能把口头描述的贪心策略写成明确、可执行的选择规则。
- 能构造小规模输入,并用最优解对照判断贪心规则是否失效。
- 能解释一个反例为什么足以否定“对所有输入都正确”的结论。
反例为什么有效
贪心算法通常声称:对任意合法输入,每一步都选择当前最优项,最终仍能得到全局最优解。这是一个全称命题。要否定它,不需要枚举全部输入,只需找到一个合法输入,使贪心结果严格差于最优结果。
以硬币集合 1、3、4 和目标金额 6 为例,“每次选不超过剩余金额的最大硬币”会得到 4 + 1 + 1,共 3 枚;最优方案是 3 + 3,只需 2 枚。因此,该规则并不适用于所有硬币系统。

构造小规模反例
可以按以下顺序检验一个看似合理的贪心规则:
- 明确规则。写清楚每一步比较什么、选择什么,以及相等时如何处理。
- 缩小输入。优先尝试 3~6 个元素、较小权值或较短区间,便于手算全部候选。
- 保留“诱饵”。让局部最优项看起来很有吸引力,但选择它后会破坏后续组合。
- 计算最优解。可用穷举、动态规划或可靠的基准算法得到对照答案。
- 比较目标值。只要贪心结果更差,就得到有效反例;若暂未发现,只能说明测试未命中,不能证明算法正确。
对找零问题,设目标金额为 、硬币种类数为 。动态规划求最少硬币数的时间复杂度为 ,足以作为小规模反例搜索的基准。
完整可运行示例
下面的 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 件物品的反例。验收条件是给出容量、每件物品的重量与价值,并证明贪心总价值小于最优总价值。
本课总结
- 一个合法反例即可否定“贪心规则对所有输入都最优”的全称结论。
- 高效构造反例的关键是缩小规模、设计局部诱饵,并用可靠算法计算最优答案。
- 未找到反例不等于已经证明正确,正确性仍需严格论证。
下一课预告
下一阶段将继续学习如何从反例检验走向正确性证明,理解哪些结构条件能够保证局部选择安全地导向全局最优。
按自己的节奏,确认真正理解。