14.1 贪心策略：局部最优 → 全局最优

贪心算法就像一个永远只看眼前利益的“小聪明”朋友——它在每一步都做出当前看起来最好的选择，希望这些局部最优解能最终拼凑成全局最优解。虽然这种方法并不总是奏效（毕竟人生不能只看眼前），但在某些特定问题上却异常有效。

贪心算法的核心思想是：在每一步决策时，都选择当前状态下最优的选项，而不考虑未来的影响。这种策略的关键在于问题必须具有贪心选择性质和最优子结构。

• 贪心选择性质：可以通过局部最优选择来构造全局最优解
• 最优子结构：问题的最优解包含其子问题的最优解

让我们通过一个简单的例子来理解这个概念：```python

贪心算法基本框架示例：找零钱问题（假设硬币面额为1, 5, 10, 25）

def greedy_coin_change(amount): """ 使用贪心策略解决找零钱问题 注意：这只在特定硬币系统下能得到最优解 """ # 定义硬币面额，按从大到小排序 coins = [25, 10, 5, 1] result = []

try:
    # 对于每个硬币面额
    for coin in coins:
        # 尽可能多地使用当前面额的硬币
        count = amount // coin
        if count > 0:
            result.extend([coin] * count)
            amount -= coin * count
        
        # 如果金额已经为0，提前结束
        if amount == 0:
            break
    
    return result

except Exception as e:
    print(f"找零钱过程中发生错误: {e}")
    return []

测试贪心找零

if name == "main": test_amount = 67 change = greedy_coin_change(test_amount) print(f"金额 {test_amount} 的贪心找零方案: {change}") print(f"共使用 {len(change)} 枚硬币")

这个例子展示了贪心算法的基本思路：每次都选择最大的可能硬币。在美国硬币系统（1, 5, 10, 25）下，这种方法确实能得到最少硬币数的最优解。但要注意，如果硬币面额是[1, 3, 4]，要凑6元的话，贪心会给出[4, 1, 1]（3枚），而最优解其实是[3, 3]（2枚）。

贪心策略的关键在于**问题是否具有贪心选择性质**。这节讲了贪心算法的基本思想和适用条件，以及通过找零钱的例子说明了其工作原理和局限性。

### 14.2 活动选择问题与区间调度

活动选择问题是贪心算法的经典应用场景，也是面试中的常客。想象你是一个超级忙碌的日程达人，收到了一堆活动邀请，每个活动都有开始时间和结束时间，而你不能同时参加两个有时间冲突的活动。那么如何选择最多的活动来参加呢？

这个问题的贪心策略很巧妙：**总是优先选择结束时间最早的活动**。为什么这样做是对的呢？因为结束得越早，留给后面活动的时间就越多，这样就能容纳更多的活动。

让我们看看具体的实现方法：

| 功能名称 | 实例调用方法 | 具体功能与注意事项 |
|---------|-------------|------------------|
| 活动选择 | `select_activities(activities)` | 输入活动列表，返回最多可参加的活动数量；需要先按结束时间排序 |
| 区间调度 | `schedule_intervals(intervals)` | 类似活动选择，但可能需要返回具体选择的区间；注意处理边界情况 |

```python
def select_activities(activities):
    """
    使用贪心算法解决活动选择问题
    activities: 列表，每个元素为(start_time, end_time)元组
    返回: 最多可以选择的活动数量
    """
    if not activities:
        return 0
    
    try:
        # 按结束时间升序排序（贪心的关键步骤）
        sorted_activities = sorted(activities, key=lambda x: x[1])
        
        # 选择第一个活动（结束时间最早的）
        count = 1
        last_end_time = sorted_activities[0][1]
        
        # 遍历剩余活动
        for i in range(1, len(sorted_activities)):
            start_time, end_time = sorted_activities[i]
            
            # 如果当前活动的开始时间 >= 上一个选中活动的结束时间
            if start_time >= last_end_time:
                count += 1
                last_end_time = end_time
        
        return count
    
    except Exception as e:
        print(f"活动选择过程中发生错误: {e}")
        return 0

# 测试活动选择
if __name__ == "__main__":
    # 每个元组表示(开始时间, 结束时间)
    activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
    max_activities = select_activities(activities)
    print(f"最多可以参加 {max_activities} 个活动")
    
    # 验证排序效果
    sorted_act = sorted(activities, key=lambda x: x[1])
    print(f"按结束时间排序后的活动: {sorted_act}")

这个算法的时间复杂度主要是排序的O(n log n)，之后的遍历是O(n)。空间复杂度是O(1)（不考虑排序的额外空间）。

如果你想要返回具体选择的活动而不是仅仅数量，只需要稍微修改一下代码，记录选中的活动索引即可。这种区间调度的思想在实际应用中非常广泛，比如会议室安排、课程表制定、CPU任务调度等。

这节介绍了活动选择问题的贪心解法，核心是按结束时间排序后贪心选择，这种方法能够保证得到最优解，并且实现简单高效。

14.3 分发饼干、跳跃游戏等典型场景

贪心算法在实际编程题中有很多经典应用场景，其中分发饼干和跳跃游戏是最具代表性的两个例子。让我们逐个来看：

分发饼干问题：假设你是一位善良的饼干分配者，有一群孩子和一堆饼干。每个孩子有一个贪心因子（表示他们满意的最小饼干尺寸），每个饼干有固定的尺寸。你的目标是尽可能满足更多的孩子。

跳跃游戏问题：你站在数组的第一个位置，数组中的每个元素代表在该位置能够跳跃的最大长度。问你是否能够到达最后一个位置。

先看分发饼干的实现：

功能名称	实例调用方法	具体功能与注意事项
分发饼干	find_content_children(g, s)	g为孩子贪心因子列表，s为饼干尺寸列表；返回最多能满足的孩子数量
跳跃游戏	can_jump(nums)	nums为跳跃数组；返回是否能到达最后位置；注意处理边界情况

def find_content_children(g, s):
    """
    分发饼干问题的贪心解法
    g: 孩子的贪心因子列表
    s: 饼干尺寸列表
    返回: 最多能满足的孩子数量
    """
    try:
        # 对两个列表都进行升序排序
        g_sorted = sorted(g)
        s_sorted = sorted(s)
        
        child_index = 0  # 当前考虑的孩子索引
        cookie_index = 0  # 当前考虑的饼干索引
        
        # 双指针遍历
        while child_index < len(g_sorted) and cookie_index < len(s_sorted):
            # 如果当前饼干能满足当前孩子
            if s_sorted[cookie_index] >= g_sorted[child_index]:
                child_index += 1  # 满足一个孩子
            
            cookie_index += 1  # 无论是否满足，都要考虑下一个饼干
        
        return child_index
    
    except Exception as e:
        print(f"分发饼干过程中发生错误: {e}")
        return 0

def can_jump(nums):
    """
    跳跃游戏的贪心解法
    nums: 跳跃数组，每个位置表示最大跳跃长度
    返回: 是否能到达最后一个位置
    """
    if not nums or len(nums) <= 1:
        return True
    
    try:
        # 记录当前能够到达的最远位置
        max_reach = 0
        
        # 遍历数组（不需要检查最后一个位置）
        for i in range(len(nums) - 1):
            # 如果当前位置已经超出了能到达的范围，说明无法继续
            if i > max_reach:
                return False
            
            # 更新能到达的最远位置
            max_reach = max(max_reach, i + nums[i])
            
            # 如果已经能到达或超过最后一个位置，提前返回
            if max_reach >= len(nums) - 1:
                return True
        
        return max_reach >= len(nums) - 1
    
    except Exception as e:
        print(f"跳跃游戏判断过程中发生错误: {e}")
        return False

# 测试分发饼干
if __name__ == "__main__":
    # 分发饼干测试
    children_greed = [1, 2, 3]
    cookies_size = [1, 1]
    satisfied = find_content_children(children_greed, cookies_size)
    print(f"最多能满足 {satisfied} 个孩子")
    
    # 跳跃游戏测试
    jump_array1 = [2, 3, 1, 1, 4]
    jump_array2 = [3, 2, 1, 0, 4]
    
    print(f"数组 {jump_array1} 能否跳到最后: {can_jump(jump_array1)}")
    print(f"数组 {jump_array2} 能否跳到最后: {can_jump(jump_array2)}")

分发饼干的贪心策略是：优先满足贪心因子小的孩子，用刚好能满足他们的最小饼干。这样可以避免大饼干被浪费在要求不高的孩子身上。

跳跃游戏的贪心策略是：在每一步都记录当前能够到达的最远位置。只要在遍历过程中发现某个位置无法到达，就直接返回false。

这两个问题都体现了贪心算法的核心思想：在当前状态下做出最好的选择，而不考虑未来的复杂情况。这种策略在这两个问题中都能得到最优解。

这节通过分发饼干和跳跃游戏两个典型例子，展示了贪心算法在不同场景下的应用思路，关键是要找到合适的贪心策略并证明其正确性。

14.4 贪心正确性证明思路简介

虽然贪心算法看起来简单直观，但要真正掌握它，必须学会如何证明贪心策略的正确性。毕竟，不是所有问题都适合用贪心来解决，盲目使用可能会得到错误答案。

贪心算法正确性证明通常有两种主要方法：

1. 交换论证（Exchange Argument） 这是最常用的方法。基本思路是：假设存在一个最优解，然后通过一系列的交换操作，将其转换成贪心算法产生的解，同时保证解的质量不会变差。

2. 数学归纳法 通过归纳法证明：如果前k步的贪心选择都是正确的，那么第k+1步的贪心选择也是正确的。

让我们用活动选择问题来演示交换论证：

假设我们有一个最优解O，它选择了活动集合{o₁, o₂, ..., oₖ}，按结束时间排序。 贪心算法选择了活动集合G = {g₁, g₂, ..., gₘ}，其中g₁是结束时间最早的活动。

如果o₁ ≠ g₁，那么由于g₁结束时间 ≤ o₁结束时间，我们可以用g₁替换o₁，得到新的解O' = {g₁, o₂, ..., oₖ}。 因为g₁结束得更早或相同，所以g₁不会与o₂冲突（原来o₁和o₂不冲突，g₁结束时间≤o₁结束时间）。 因此O'也是一个可行解，且大小与O相同，所以也是最优解。

通过这样的交换，我们可以逐步将任何最优解转换成贪心解，从而证明贪心解的最优性。

def validate_greedy_correctness():
    """
    验证贪心算法正确性的辅助函数示例
    这里以小规模的活动选择问题为例，通过穷举验证贪心解的最优性
    """
    import itertools
    
    def brute_force_max_activities(activities):
        """暴力求解最大活动数量（仅用于小规模验证）"""
        max_count = 0
        n = len(activities)
        
        # 枚举所有可能的子集
        for r in range(1, n + 1):
            for subset in itertools.combinations(activities, r):
                # 检查子集是否有效（无时间冲突）
                sorted_subset = sorted(subset, key=lambda x: x[0])  # 按开始时间排序
                valid = True
                for i in range(len(sorted_subset) - 1):
                    if sorted_subset[i][1] > sorted_subset[i + 1][0]:
                        valid = False
                        break
                
                if valid:
                    max_count = max(max_count, len(subset))
        
        return max_count
    
    def test_greedy_vs_brute_force():
        """测试贪心算法与暴力算法的结果是否一致"""
        test_cases = [
            [(1, 3), (2, 4), (3, 5)],
            [(1, 4), (2, 3), (4, 6), (5, 7)],
            [(1, 2), (2, 3), (3, 4), (4, 5)]
        ]
        
        for i, activities in enumerate(test_cases):
            greedy_result = select_activities(activities)
            brute_result = brute_force_max_activities(activities)
            
            print(f"测试用例 {i+1}: 贪心={greedy_result}, 暴力={brute_result}, 正确={greedy_result == brute_result}")
    
    return test_greedy_vs_brute_force

# 运行正确性验证
if __name__ == "__main__":
    validator = validate_greedy_correctness()
    validator()

需要注意的是，在实际面试或竞赛中，通常不需要写出完整的数学证明，但你应该能够清晰地解释为什么你的贪心策略是正确的。

另外，有一些经典的反例可以帮助我们理解贪心算法的局限性：

• 0-1背包问题：不能用贪心（按价值密度排序），必须用动态规划
• 某些图的最短路径问题：如果存在负权边，Dijkstra算法（贪心）就不适用

总的来说，贪心算法的正确性证明需要具体情况具体分析，但掌握交换论证和归纳法这两种基本方法，就能应对大部分场景。

这节介绍了贪心算法正确性证明的基本思路，包括交换论证和数学归纳法，并通过活动选择问题的例子说明了如何应用这些证明方法。