第 63 课：贪心算法入门

1. 学习目标

完成本课学习后，你将能够：

理解贪心算法的核心思想：每一步都做出在当前看来最优的选择，以期最终得到全局最优解。
识别哪些问题适合使用贪心算法（具有贪心选择性质和最优子结构性质）。
实现基于贪心策略的算法来解决基础问题（如零钱兑换）。
分析贪心算法与动态规划等算法的异同与适用场景。

2. 核心概念

想象一下，你面前有一堆大小不一的宝石，你有一个容量固定的背包。你的目标是尽可能多地装走宝石的价值。一个“贪心”的策略是：每次都从剩余宝石中挑选当前价值最高的那个放入背包，直到背包装满。这就是贪心算法的本质——总是做出局部最优的选择，期望这些选择的叠加能导向全局最优解。

贪心算法有两个关键特征：

贪心选择性质：可以通过做出局部最优选择（贪心选择）来构造全局最优解。也就是说，你不需要考虑未来，也不需要回头修改已经做的选择。
最优子结构性质：原问题的最优解包含其子问题的最优解。

核心步骤：

建立数学模型：将问题抽象，明确每一步的“选择”是什么，以及“最优”的标准是什么（如最小代价、最大收益）。
制定贪心策略：确定在每一步，根据什么标准来做出局部最优选择。
证明策略的正确性：这是最难也是最关键的一步。我们需要证明，通过这个贪心策略得到的局部最优解，确实能组合成全局最优解。这通常需要使用交换论证等技巧。
设计算法：实现这个贪心策略。

重要提示：贪心算法并不是万能的。对于某些问题，局部最优选择会导致无法得到全局最优解。在这种情况下，需要考虑动态规划等其他算法。

3. 代码示例

我们以经典的“零钱兑换”问题为例，但请注意，这里我们讨论的是在特定条件下（如硬币面额是“规范”的，例如美国货币系统）可以用贪心求解的版本。这个问题能很好地展示贪心的思路。

问题：给定不同面额的硬币（例如 [1, 5, 10, 25] 美分）和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。假设每种硬币的数量是无限的。

贪心策略：为了用最少的硬币数，我们应该尽可能多地使用大面额的硬币。这是一个直观的局部最优选择——使用一个大硬币比使用多个小硬币能更快地减少剩余金额。

def coin_change_greedy(coins, amount):
    """
    使用贪心算法计算最少硬币数 (适用于“规范”的硬币系统，如 [1, 5, 10, 25])。
    
    参数:
    coins: 硬币面额列表，例如 [1, 5, 10, 25]。
    amount: 需要凑成的总金额。
    
    返回:
    所需的最少硬币数，如果无法凑成则返回 -1。
    """
    # 为了能从大到小选择硬币，先对硬币面额进行降序排序
    coins.sort(reverse=True)
    
    coin_count = 0  # 记录使用的硬币总数
    remaining = amount # 剩余需要凑的金额
    
    # 遍历每种面额的硬币
    for coin in coins:
        # 计算当前面额硬币最多能使用多少个
        num_coins = remaining // coin
        # 使用这些硬币
        coin_count += num_coins
        # 更新剩余金额
        remaining -= num_coins * coin
        
        # 如果剩余金额为0，说明已经凑齐，提前结束循环
        if remaining == 0:
            break
            
    # 最终检查：如果剩余金额不为0，说明无法凑齐
    return coin_count if remaining == 0 else -1

# 测试代码
if __name__ == "__main__":
    # 示例1：美国货币系统，贪心有效
    coins1 = [1, 5, 10, 25]
    amount1 = 30
    result1 = coin_change_greedy(coins1, amount1)
    print(f"金额 {amount1} 美分, 使用硬币 {coins1}") # 预期输出: 2 (25+5)
    print(f"最少硬币数: {result1}\n")

    # 示例2：一个贪心可能失效的例子（[1, 3, 4], amount=6）
    # 贪心会先用4，剩下2，需要两个1，共3枚硬币。
    # 但最优解是两个3，共2枚硬币。
    coins2 = [1, 3, 4]
    amount2 = 6
    result2 = coin_change_greedy(coins2, amount2)
    print(f"金额 {amount2}, 使用硬币 {coins2}")
    print(f"贪心算法得到的最少硬币数: {result2}") # 输出 3
    print(f"但最优解是 3+3=2 枚硬币。")

代码解读：

我们首先将硬币按面额从大到小排序，这是实现“先选大面额”贪心策略的关键。
然后，我们遍历每种硬币。对于当前面额的硬币，我们计算最多能用多少个（remaining // coin），并将这些硬币计入总数，同时更新剩余金额。
如果剩余金额提前归零，循环提前结束。
最后，检查剩余金额是否为零。如果不是零，说明无法用给定的硬币恰好凑出目标金额，返回-1。

4. 实践练习

练习 1：分糖果 (简单) 有 m 个糖果和 n 个孩子。每个孩子有一个贪婪因子 g[i]，即孩子需要的糖果尺寸的最小值。每个糖果有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将糖果 j 分给孩子 i，该孩子会得到满足。目标是尽可能满足更多的孩子。要求：使用贪心策略（优先将糖果分配给贪婪因子小的孩子，或优先将小糖果分配给能被满足的孩子）来求解最多能满足的孩子数量。提示：对孩子的贪婪因子和糖果的尺寸分别进行排序。

输入示例：

g = [1, 2, 3], s = [1, 1]

预期输出：

（一个尺寸为1的糖果可以满足贪婪因子为1的孩子）

练习 2：区间调度问题 (中等) 给定一组区间 intervals = [[s1, e1], [s2, e2], ...]，其中 s_i 是开始时间，e_i 是结束时间。请找出最多有多少个区间互不重叠。要求：使用贪心策略（例如，优先选择结束时间最早的区间）。 输入示例：

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

预期输出：

（可以选择 [1,2], [2,3], [3,4]）

练习 3：跳跃游戏 (中等偏难) 给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。要求：尝试设计一个贪心算法来解决此问题。 输入示例 1：

nums = [2,3,1,1,4]

预期输出 1：

true

输入示例 2：

nums = [3,2,1,0,4]

预期输出 2：

false

5. 常见错误

盲目使用贪心：没有验证问题是否满足“贪心选择性质”，就直接套用贪心模板。例如，在面额为 [1, 3, 4] 的零钱兑换问题中，用前述贪心策略会得到错误结果（金额6时输出3，但最优解是2）。关键：在使用贪心前，应尝试证明其正确性，或寻找反例。
排序标准选择错误：贪心策略往往依赖于对数据进行排序。排序的标准（如按开始时间、结束时间、重量、价值密度等）直接决定了策略的正确性。需要根据问题仔细推导正确的排序依据。
忽略问题边界条件：例如，在跳跃游戏中，需要特别处理当数组长度为0或1的情况，或者当某个位置的跳跃值为0时可能卡住的情况。
混淆贪心与动态规划：贪心是“一往无前”的，每一步选择后状态唯一确定。而动态规划会保留所有可能的状态，并通过比较这些状态来得到最优解。当一个问题的当前选择会影响未来一系列选择，并且最优解不依赖于未来的具体路径时，可能更适合用动态规划。

6. 小结

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
适用条件：问题必须具备贪心选择性质和最优子结构。
核心步骤：明确选择标准 -> 制定贪心策略 -> 证明正确性 -> 设计算法。
典型应用：活动选择、分数背包、哈夫曼编码、Dijkstra算法、Prim算法等。
重要警告：贪心策略的局部最优不一定导致全局最优。使用前务必验证或证明。对于无法用贪心完美解决的问题，应考虑动态规划。

贪心算法的魅力在于其直观和高效，但它的“贪婪”也常常是它的陷阱。理解其原理和局限性，是正确应用它的第一步。在接下来的课程中，我们将通过更经典的“活动选择问题”来深入体会贪心算法的设计与证明过程。

练习编辑器

rust