贪心算法：短视的猎人

算法背后的故事：找零钱

想象你是一名收银员。一个顾客需要 41 美分的零钱。你手里有 25、10、5 和 1 美分的硬币。 你如何用最少数量的硬币凑齐零钱？

很自然地，你会先拿最大的硬币：

1. 拿一个 25¢ 硬币 (还剩: 16¢)
2. 拿一个 10¢ 硬币 (还剩: 6¢)
3. 拿一个 5¢ 硬币 (还剩: 1¢)
4. 拿一个 1¢ 硬币 (还剩: 0¢)

总计：4 枚硬币。 这种“先拿最大的”策略就是 贪心算法。你没有考虑未来；你只是抓住了眼下最好的东西。对于许多货币体系来说，这种贪心选择确实就是最优解。

为什么需要它？

• 速度： 贪心算法通常是 $O(N)$ 或 $O(N \log N)$。它们比动态规划快得多。
• 网络： Dijkstra 算法（最短路径）和 Prim 算法（最小生成树）都是贪心策略。
• 压缩： 哈夫曼编码使用贪心策略来构建最优树。
• 调度： 在一个房间里安排尽可能多的会议。

算法是如何“思考”的

该算法是一个顺序决策者。

1. 选择： 从当前集合中挑选“最佳”候选者。
2. 可行性： 检查这个候选者是否违反了任何规则。
3. 不可逆性： 一旦选定，绝不回头。贪心算法没有“撤销”按钮。

贪心选择性质： 贪心算法仅在“局部最优解能导致全局最优解”时有效。

• 陷阱： 如果你有 25、20 和 1 美分的硬币，而你需要找 40 美分的零钱……
  • 贪心策略：25 + 1 + 1… (需要 16 枚硬币)
  • 实际最优：20 + 20 (只需要 2 枚硬币) 在这种情况下，短视的猎人就翻车了。

工程决策：“足够好”的方案

在许多复杂的工程问题中（如旅行商问题），寻找完美答案可能需要几年的计算。

• 工程师通常使用 贪心启发式算法 (Greedy Heuristics) 在 10 毫秒内找到一个“95% 完美”的答案。
• 在生产环境中，一个快速且还不错的答案往往优于一个缓慢但完美的答案。

实现参考 (Python)

# 区间调度问题：在一个房间内安排最多的会议
def schedule_meetings(meetings):
    # meetings = [(开始时间, 结束时间), ...]
    
    # 1. 贪心选择：按“结束时间”排序
    # 一个会议结束得越早，留给后面会议的空间就越大
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end_time = 0
    selected = []

    for start, end in meetings:
        if start >= last_end_time:
            # 2. 可行性检查：不重叠？是的。
            count += 1
            last_end_time = end
            selected.append((start, end))
            
    return count, selected

# 使用示例
mtgs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(f"最大会议数: {schedule_meetings(mtgs)}")

小结

贪心算法教会我们：有时候，专注比规划更重要。 通过无情地追求眼前的最优方案，我们可以用最小的代价解决复杂问题。它提醒我们，虽然我们应该追求最好的结果，但我们也必须尊重时间和复杂性的成本。