贪心法入门：从吃自助餐到解决问题

想象一下，你去吃自助餐，每次只能拿一盘菜。你会怎么做？当然先拿自己最爱吃的，然后从剩下的菜里再挑最喜欢的，不断重复。这种“每次选当前最好”的思维方式，就是贪心法的核心。贪心法是一种简单高效的算法，它通过每一步都选择当前看起来最优的方案，希望最终能得到全局最优的结果。

但贪心法真的每次都能成功吗？不一定。就像你为了喝汤放弃主食，最后可能没吃饱。所以贪心法只适用于那些“局部最优能推出全局最优”的问题。下面让我们一步步弄明白它。

一、贪心法的核心思想——局部最优 → 全局最优

贪心法的策略就是：面对一个问题，每次只考虑当前能做出的最好选择，不考虑未来可能的影响。然后一直重复，直到问题解决。

生活中的例子

1. 排队买冰淇淋：假设你排在长长的队伍里，但你知道不同窗口的冰淇淋口味不同。你只能选一个窗口排队。你的贪心策略是：先看哪个窗口前面人最少，就排那个队。这样你就能尽快买到冰淇淋。但可能人最少的窗口卖的冰淇淋口味你不喜欢？这里你选择了“等待时间最短”作为局部最优标准。

2. 零花钱分配：你每天有10元零花钱，想攒钱买一个50元的玩具。你的贪心策略是：每天不花任何钱，把10元都存起来。这样5天就攒够了。局部最优（每天存款）导致全局最优（最快买到）。

关键理解

贪心法并不是“一次性把所有选择看一遍”，而是每次只做一个局部决策，并且这个决策一旦做出就不能反悔。它不像回溯法那样尝试所有可能，所以速度很快。

二、什么时候能用贪心？——两个重要性质

贪心法不是万能的，用之前必须判断问题是否满足下面两个性质：

1. 贪心选择性质

每一步的局部最优选择，最终能导出全局最优解。也就是说，我们可以直接选当前最好的，不用担心这个选择会破坏后面的机会。

2. 最优子结构性质

一个问题的最优解包含其子问题的最优解。也就是说，如果你已经解决了前面一小块问题，剩下的问题也能用同样的贪心策略得到最优。

硬币找零问题（经典正反例）

正例：美元硬币（1分、5分、10分、25分）

你要找零63分，用最少的硬币。按照贪心策略：每次选面值最大且不超过剩余金额的硬币。

• 剩余63分，最大面值25分 → 拿一个，剩38分
• 剩38分，再拿一个25分 → 剩13分
• 剩13分，最大面值10分 → 拿一个，剩3分
• 剩3分，拿三个1分 → 用了1个10分，3个1分

总共用了2个25分 + 1个10分 + 3个1分 = 6枚硬币。这是最优解，因为美元硬币的面额设计恰好满足贪心性质。

反例：自定义硬币（1分、3分、4分）

你要找零6分，用最少的硬币。贪心策略：

• 剩余6分，最大面值4分 → 拿一个，剩2分
• 剩2分，最大面值1分 → 拿两个1分

总共用了3枚硬币（4+1+1）。但最优解是2枚（3+3）。为什么贪心失败了？因为贪心选择的4分虽然当前最大，但导致后面需要两枚1分，而用两个3分更好。这说明此问题不满足贪心选择性质——局部最优（选4分）没有导致全局最优。

三、经典应用：活动安排问题

假设你周末想参加多个课外活动，每个活动都有开始时间和结束时间。你最多能参加多少个互不冲突的活动？

贪心策略： 每次选结束时间最早的活动，然后跳过所有和它冲突的活动，再从剩下的活动中选结束时间最早的。

例子

活动：

• 画画：9:00 ~ 10:30
• 舞蹈：9:30 ~ 11:00
• 围棋：10:30 ~ 11:30
• 机器人：11:00 ~ 12:00

按照结束时间排序：画画(10:30)、舞蹈(11:00)、围棋(11:30)、机器人(12:00)。

1. 选结束最早的画画（9:00~10:30），跳过与其重叠的舞蹈（9:30开始，冲突）。
2. 剩余可选：围棋（10:30开始，不冲突）、机器人（11:00开始，不冲突）。选结束最早的围棋（10:30~11:30）。
3. 再选机器人（11:00开始？与围棋冲突，跳过）。最终选了画画和围棋，共两个活动。
   实际上最优也是两个（画画+机器人也能得到两个，但贪心得到了另一个方案，也是最优）。

Python 代码实现

# 活动安排：返回最多能参加的活动数量
def max_activities(activities):
    """
    activities: 列表，每个元素为 (开始时间, 结束时间)
    返回可参加的最大活动数
    """
    # 按结束时间从小到大排序
    activities.sort(key=lambda x: x[1])
    
    count = 0          # 已选活动数量
    last_end = 0       # 上一个活动的结束时间
    for start, end in activities:
        if start >= last_end:  # 不冲突
            count += 1
            last_end = end
    return count

# 测试
act = [(9, 10.5), (9.5, 11), (10.5, 11.5), (11, 12)]
print("最多可参加活动数:", max_activities(act))  # 输出 2

四、新手容易犯的错误

错误1：没有排序就贪心

贪心往往需要先对数据排序（如硬币面额降序、活动结束时间升序）。如果不排序，按照原始顺序依次选“当前最好”，可能错过全局最优。例如活动安排问题若按开始时间排序，可能会选出占用时间长的活动，减少总数量。

错误2：盲目相信贪心

有些问题看似可以贪心，实际不行。比如上面的自定义硬币（1,3,4）找零6分，贪心给出错误答案。新手拿到问题容易直接用贪心，而忘了验证贪心选择性质。做题时一定要先思考是否满足性质，或者试着举几个反例。

错误3：忽略细节条件

比如硬币问题中，如果零钱面额没有排序，代码里要先排序。还有活动安排中，时间比较可能是浮点数或整数，要小心边界条件（如一个活动结束等于另一个开始是否冲突？通常认为不冲突，因为可以无缝衔接）。

五、完整可运行的代码示例

下面是一个完整的程序，包含两种贪心问题的实现：美元硬币找零和活动安排。

# ---------- 1. 硬币找零（美元硬币） ----------
def greedy_coin_change(amount, coins):
    """
    返回用coins面值（降序）找零amount所需的最少硬币数
    注意：此算法只在硬币面额满足贪心性质时正确（如美元硬币）
    """
    coins.sort(reverse=True)  # 从大到小排序
    coin_count = 0
    remaining = amount
    for coin in coins:
        while remaining >= coin:
            remaining -= coin
            coin_count += 1
    return coin_count

# 测试：找零63美分
print("找零63美分需要硬币数:", greedy_coin_change(63, [1, 5, 10, 25]))  # 输出6

# ---------- 2. 活动安排 ----------
def max_activities(activities):
    """
    activities: 列表，每个元素为 (开始时间, 结束时间)
    返回可参加的最大活动数
    """
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    count = 0
    last_end = 0
    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# 测试
act = [(9, 10.5), (9.5, 11), (10.5, 11.5), (11, 12)]
print("最多可参加活动数:", max_activities(act))  # 输出2

# 另一个测试：全部不冲突
act2 = [(1,2), (2,3), (3,4)]
print("不冲突活动数:", max_activities(act2))  # 输出3

运行结果：

找零63美分需要硬币数: 6
最多可参加活动数: 2
不冲突活动数: 3

六、相关指引

贪心法适合解决最优子结构且贪心选择性明显的问题。如果你遇到一个问题，先思考能否用贪心，再考虑别的算法：

• 如果不能贪心，可以尝试 动态规划（DP）。动态规划会记录所有可能的子问题解，能处理更复杂的情况（如自定义硬币找零）。
• 如果问题需要所有解而非最优解，可以尝试 回溯法 或 深度优先搜索。
• 如果问题规模很大，贪心无法保证最优，也可以作为近似算法使用（例如背包问题的分数背包可以用贪心，但0-1背包不行）。

总之，贪心法是一种非常实用且高效的算法，但一定要先分析问题是否适用。多练习、多举反例，你就能逐渐掌握它的使用时机。