编辑“︁贪心算法的局限性”︁（章节）

=== 贪心算法的局限性 ===

==== 1. 无法保证全局最优解 ====
贪心算法在每一步只考虑当前的最优选择，而忽略了未来可能的影响。因此，它可能陷入局部最优，而无法达到全局最优。

'''示例：硬币找零问题（非贪心友好版本）'''
假设硬币面额为 <math>\{1, 3, 4\}</math>，目标是找零 6。贪心算法会选择：
1. 选择最大的 4，剩余 2。
2. 选择两个 1，共使用 3 枚硬币（4, 1, 1）。
然而，最优解是两枚 3 硬币（3, 3）。

<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>

==== 2. 依赖问题的特定结构 ====
贪心算法仅在问题具有贪心选择性质时有效。例如，[[霍夫曼编码]]和[[Dijkstra算法]]适用贪心策略，但许多问题（如背包问题）需要动态规划或其他方法。

'''示例：0-1 背包问题'''
在 0-1 背包问题中，贪心算法按价值或单位价值排序可能无法得到最优解。例如：
- 物品：[(重量: 10, 价值: 60), (重量: 20, 价值: 100), (重量: 30, 价值: 120)]
- 背包容量：50。
贪心按单位价值排序会选择物品 1 和 2（总价值 160），但最优解是物品 2 和 3（总价值 220）。

==== 3. 无法回溯或撤销选择 ====
贪心算法一旦做出选择就无法撤销，而动态规划等算法可以通过状态转移重新评估。