Part 7.1：贪心算法——局部最优通向全局最优的艺术

引言：当”自私”成为一种智慧

想象你正在玩一个闯关游戏，每一关都有多条路径可选，每条路径上都有不同数量的金币。你的目标是收集尽可能多的金币。此时，你会采用什么策略？

一种直觉的做法是：在每一关都选择当前能拿到最多金币的那条路。这种”走一步看一步，每步都选最好”的策略，就是贪心算法 (Greedy Algorithm) 的核心思想。

但问题来了：这种”目光短浅”的策略，真的能保证最终拿到最多的金币吗？答案是：不一定。这正是贪心算法最迷人也最具挑战性的地方——它简单、高效、直观，但并非对所有问题都有效。

为什么贪心算法如此重要？

面试价值：

贪心算法是大厂面试的高频考点（Google、字节、腾讯等）
能够快速判断一个问题是否适合用贪心求解，是算法思维成熟的标志
许多看似复杂的问题，用贪心思想能得到优雅的 O(n log n) 甚至 O(n) 解法

学术与工程价值：

贪心算法是许多经典算法的基础（如 Dijkstra、Prim、Kruskal）
在资源调度、任务分配、网络路由等实际工程问题中广泛应用
理解贪心算法，能帮助你更好地理解”局部最优”与”全局最优”的关系

本文将带你系统学习贪心算法的核心思想、适用条件、证明方法，以及如何判断一个问题能否用贪心求解。

背景知识：算法设计的三大范式

在深入贪心算法之前，我们需要了解算法设计的三大主要范式：

1. 暴力枚举 (Brute Force)

思想：尝试所有可能的解，选择最优的那个
优点：一定能找到正确答案
缺点：时间复杂度通常是指数级 O(2^n) 或 O(n!)
例子：旅行商问题的暴力解法

2. 动态规划 (Dynamic Programming)

思想：将问题分解为子问题，保存子问题的解，避免重复计算
优点：能解决很多复杂问题，时间复杂度通常是多项式级
缺点：需要额外的空间存储子问题的解
例子：背包问题、最长公共子序列

3. 贪心算法 (Greedy Algorithm)

思想：每一步都做出当前看起来最好的选择
优点：实现简单，效率高，通常是 O(n log n) 或 O(n)
缺点：不是对所有问题都有效，需要满足特定条件
例子：找零钱问题、活动选择问题

核心区别：动态规划会”回头看”（考虑之前的所有选择），而贪心算法”不回头”（只关注当前最优）。

详细算法原理

直觉：贪心的本质

贪心算法的核心思想可以用一句话概括：

在每一步选择中，都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的。

用更通俗的话说：走一步看一步，每步都选最好的，希望最后整体也是最好的。

这就像你在爬山时，每次都选择当前看起来最陡峭的上坡路（局部最优），希望最终能到达山顶（全局最优）。但问题是，这种策略可能让你爬到一个小山包上，而错过了真正的山顶。

严谨原理：贪心算法的两大性质

一个问题能够用贪心算法求解，必须满足两个关键性质：

1. 贪心选择性质 (Greedy Choice Property)

定义：一个问题的全局最优解可以通过一系列局部最优选择得到。

通俗理解：你可以放心地做出当前看起来最好的选择，而不用担心这个选择会影响后续的最优性。

数学表述：设问题的一个最优解为 S = {s₁, s₂, …, sₙ}，如果存在一个贪心选择 g，使得 S’ = {g, s₂, …, sₙ} 也是最优解，则该问题具有贪心选择性质。

2. 最优子结构 (Optimal Substructure)

定义：一个问题的最优解包含其子问题的最优解。

通俗理解：如果你已经做出了一个贪心选择，那么剩下的问题也可以用同样的贪心策略求解。

数学表述：设问题 P 的最优解为 OPT(P)，如果 OPT(P) 包含子问题 P’ 的最优解 OPT(P’)，则该问题具有最优子结构。

注意：最优子结构是动态规划和贪心算法的共同特征，但贪心选择性质是贪心算法独有的。

关键图示

图示：贪心算法 vs 动态规划的决策树
贪心算法的决策过程：
起点 → [选择A] → 子问题1 → [选择C] → 子问题2 → ... → 终点
        ↓ (只考虑当前最优)
     放弃B
特点：每一步只保留一个分支（当前最优），不回溯。
动态规划的决策过程：
起点 → [选择A] → 子问题1 → [选择C] → ...
     ↘         ↗
       [选择B] → 子问题2 → [选择D] → ...
        (保存所有可能的状态)
特点：保留所有可能的状态，通过比较选择最优。

步骤分解：贪心算法的设计流程

设计一个贪心算法通常遵循以下步骤：

Step 1：将问题分解为子问题

明确问题的目标和约束
思考如何将问题分解为一系列决策

Step 2：确定贪心策略

在每一步，定义什么是”最优选择”
这是贪心算法设计的核心，也是最难的部分

Step 3：证明贪心选择性质

证明局部最优选择不会影响全局最优
常用方法：反证法、交换论证法

Step 4：证明最优子结构

证明做出贪心选择后，剩余问题仍然可以用贪心求解

Step 5：实现算法

将贪心策略转化为代码
通常需要排序或使用优先队列

动画式案例：找零钱问题

问题描述：假设有面值为 1、5、10、25 的硬币，要找给顾客 41 元，如何用最少的硬币？

贪心策略：每次都选择不超过剩余金额的最大面值硬币。

步骤变化

初始状态：

剩余金额：41
已用硬币：[]

第1步：选择面值 25 的硬币

剩余金额：41 - 25 = 16
已用硬币：[25]

第2步：选择面值 10 的硬币

剩余金额：16 - 10 = 6
已用硬币：[25, 10]

第3步：选择面值 5 的硬币

剩余金额：6 - 5 = 1
已用硬币：[25, 10, 5]

第4步：选择面值 1 的硬币

剩余金额：1 - 1 = 0
已用硬币：[25, 10, 5, 1]

最终结果：使用 4 枚硬币

注意：这个贪心策略对于美国硬币系统是正确的，但对于任意硬币系统不一定正确！例如，如果硬币面值是 [1, 3, 4]，找零 6 元，贪心会选 [4, 1, 1]（3枚），但最优解是 [3, 3]（2枚）。

伪代码

标准化贪心算法框架

// 贪心算法的通用框架
function GreedyAlgorithm(problem):
    // 1. 初始化
    solution = empty_set
    remaining_problem = problem
    
    // 2. 循环直到问题解决
    while remaining_problem is not solved:
        // 3. 做出贪心选择
        choice = select_best_choice(remaining_problem)
        
        // 4. 检查选择的可行性
        if choice is feasible:
            // 5. 将选择加入解集
            solution.add(choice)
            
            // 6. 更新剩余问题
            remaining_problem = update_problem(remaining_problem, choice)
        else:
            // 如果无可行选择，返回失败
            return FAILURE
    
    // 7. 返回解
    return solution

// 关键函数：选择当前最优
function select_best_choice(problem):
    // 根据贪心策略，从候选集中选择最优的一个
    candidates = get_all_candidates(problem)
    best = candidates[0]
    
    for each candidate in candidates:
        if is_better(candidate, best):
            best = candidate
    
    return best

Python 实现

案例1：找零钱问题（完整实现）

def coin_change_greedy(coins, amount):
    """
    使用贪心算法解决找零钱问题
    
    参数:
        coins: 硬币面值列表（必须是降序排列）
        amount: 需要找零的金额
    
    返回:
        (硬币数量, 使用的硬币列表) 或 None（无法找零）
    """
    # 确保硬币按降序排列
    coins = sorted(coins, reverse=True)
    
    result = []  # 存储使用的硬币
    remaining = amount  # 剩余需要找零的金额
    
    # 贪心策略：每次选择最大的硬币
    for coin in coins:
        # 计算当前面值的硬币可以使用多少枚
        count = remaining // coin
        
        if count > 0:
            # 添加到结果中
            result.extend([coin] * count)
            # 更新剩余金额
            remaining -= coin * count
        
        # 如果已经找完零，提前退出
        if remaining == 0:
            break
    
    # 检查是否成功找零
    if remaining == 0:
        return len(result), result
    else:
        return None  # 无法精确找零

# 测试案例
print("=== 找零钱问题 ===")
coins = [25, 10, 5, 1]
amount = 41

result = coin_change_greedy(coins, amount)
if result:
    count, used_coins = result
    print(f"找零 {amount} 元需要 {count} 枚硬币")
    print(f"使用的硬币：{used_coins}")
else:
    print(f"无法精确找零 {amount} 元")

# 输出:
# 找零 41 元需要 4 枚硬币
# 使用的硬币：[25, 10, 5, 1]

案例2：活动选择问题

def activity_selection(activities):
    """
    活动选择问题：选择最多的互不冲突的活动
    
    参数:
        activities: 活动列表，每个活动是 (start_time, end_time)
    
    返回:
        选中的活动列表
    """
    # 贪心策略：按结束时间排序，优先选择结束早的活动
    activities = sorted(activities, key=lambda x: x[1])
    
    selected = []  # 已选择的活动
    last_end_time = 0  # 上一个活动的结束时间
    
    for start, end in activities:
        # 如果当前活动的开始时间 >= 上一个活动的结束时间
        # 说明不冲突，可以选择
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end
    
    return selected

# 测试案例
print("\n=== 活动选择问题 ===")
activities = [
    (1, 4),   # 活动1: 1点到4点
    (3, 5),   # 活动2: 3点到5点
    (0, 6),   # 活动3: 0点到6点
    (5, 7),   # 活动4: 5点到7点
    (3, 9),   # 活动5: 3点到9点
    (5, 9),   # 活动6: 5点到9点
    (6, 10),  # 活动7: 6点到10点
    (8, 11),  # 活动8: 8点到11点
    (8, 12),  # 活动9: 8点到12点
    (2, 14),  # 活动10: 2点到14点
    (12, 16)  # 活动11: 12点到16点
]

selected = activity_selection(activities)
print(f"最多可以选择 {len(selected)} 个活动")
print(f"选中的活动：{selected}")

# 输出:
# 最多可以选择 4 个活动
# 选中的活动：[(1, 4), (5, 7), (8, 11), (12, 16)]

时间复杂度推导过程

找零钱问题

分析：

排序硬币：O(k log k)，其中 k 是硬币种类数
遍历每种硬币：O(k)
每种硬币的计算：O(1)

总时间复杂度：O(k log k)

由于硬币种类 k 通常是常数（如 4 种），实际上可以认为是 **O(1)**。

活动选择问题

分析：

排序活动：O(n log n)，其中 n 是活动数量
遍历活动：O(n)
每个活动的判断：O(1)

总时间复杂度：O(n log n)

排序是瓶颈操作。

空间复杂度推导过程

找零钱问题

分析：

存储结果列表：最坏情况下需要 O(amount) 个硬币（全是面值1）
其他变量：O(1)

总空间复杂度：O(amount)

活动选择问题

分析：

存储选中的活动：最多 O(n) 个
排序可能需要额外空间：O(n)（取决于排序算法）

总空间复杂度：O(n)

优势 / 劣势 / 易错点

优势

实现简单：贪心算法的代码通常非常简洁，易于理解和实现
效率高：时间复杂度通常是 O(n log n) 或 O(n)，远优于动态规划的 O(n²) 或 O(n³)
空间占用小：通常只需要 O(1) 或 O(n) 的额外空间
直观：贪心策略往往符合人的直觉，容易想到

劣势

适用范围窄：只对满足贪心选择性质和最优子结构的问题有效
难以证明正确性：判断一个问题是否适合用贪心求解，需要严格的数学证明
容易出错：看似合理的贪心策略可能给出错误答案
无法处理所有情况：对于某些问题，贪心只能给出近似解，而非最优解

易错点

错误的贪心策略

# 错误示例：背包问题用贪心（应该用动态规划）
# 贪心策略：按价值排序
# 这对 0-1 背包是错误的！

忘记排序

# 错误：直接遍历，没有按贪心策略排序
for activity in activities:  # 应该先排序！
    ...

边界条件处理不当

# 错误：没有检查剩余金额是否为0
if remaining == 0:  # 必须检查！
    return result

贪心策略选择错误

# 活动选择问题
# 错误策略1：选择持续时间最短的活动
# 错误策略2：选择开始时间最早的活动
# 正确策略：选择结束时间最早的活动

适用场景

适合用贪心的问题

活动选择问题：选择最多的互不冲突的活动
霍夫曼编码：构建最优前缀编码
最小生成树：Kruskal 和 Prim 算法
单源最短路径：Dijkstra 算法（非负权图）
分数背包问题：可以拆分物品的背包问题
区间覆盖问题：用最少的区间覆盖所有点

不适合用贪心的问题

0-1 背包问题：物品不可拆分，需要用动态规划
**旅行商问题 (TSP)**：需要考虑全局路径，贪心只能给出近似解
最长公共子序列：需要考虑多种可能性，用动态规划
任意硬币系统的找零：贪心不一定给出最优解

判断方法

如何判断一个问题是否适合用贪心？

尝试构造反例：如果能找到贪心策略失败的例子，说明不适合
证明贪心选择性质：能否证明局部最优导致全局最优？
检查最优子结构：做出贪心选择后，剩余问题是否独立？
参考经典问题：该问题是否与已知的贪心问题相似？

扩展算法 & 进阶方向

1. 贪心算法的证明方法

交换论证法 (Exchange Argument)

证明任何最优解都可以通过一系列交换变成贪心解
常用于活动选择、区间调度等问题

反证法

假设贪心解不是最优解，推导出矛盾
适用于简单的贪心问题

2. 近似算法

当贪心无法给出最优解时，可以用于设计近似算法：

集合覆盖问题：贪心给出 O(log n) 近似比
旅行商问题：贪心给出 2-近似解

3. 在线算法

贪心思想在在线算法中的应用：

缓存替换算法：LRU、LFU
负载均衡：最少连接数策略

4. 经典贪心问题

霍夫曼编码 (Huffman Coding)

构建最优前缀编码树
应用于数据压缩

区间调度问题

变种：带权重的活动选择
变种：最少会议室问题

分数背包问题

与 0-1 背包的对比
贪心策略：按性价比排序

总结

贪心算法是一种强大而优雅的算法设计范式。它的核心思想简单直观：每一步都做出当前最优的选择，希望最终达到全局最优。

核心要点

✅ 两大性质：贪心选择性质 + 最优子结构
✅ 设计流程：分解问题 → 确定策略 → 证明正确性 → 实现算法
✅ 时间复杂度：通常是 O(n log n)（排序）或 O(n)（遍历）
✅ 适用条件：必须满足贪心选择性质，否则可能得到错误答案
✅ 判断方法：构造反例、证明性质、参考经典问题

与动态规划的对比

特性	贪心算法	动态规划
决策方式	局部最优	全局最优
是否回溯	不回溯	需要回溯
时间复杂度	通常更低	通常更高
适用范围	较窄	较广
正确性	需要证明	一般正确