贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（局部最优）的决策，从而希望导致全局最优解的算法策略。贪心算法通常高效且易于实现，但并非所有问题都适用，其正确性需要严格证明。

核心思想

贪心算法的核心是“局部最优导致全局最优”。它不回溯之前的决策，也不考虑未来的可能性，仅基于当前信息做出选择。其关键特性包括：

• 贪心选择性质：每一步的局部最优选择能构成全局最优解。
• 最优子结构：问题的最优解包含其子问题的最优解。

算法步骤

贪心算法的一般步骤如下：

1. 将问题分解为多个子问题。
2. 对每个子问题求解局部最优解。
3. 将局部最优解合并为全局解。

代码示例

以下是一个经典的贪心算法问题——找零钱问题的Python实现：

  
def coin_change(coins, amount):  
    coins.sort(reverse=True)  # 按面额从大到小排序  
    result = []  
    for coin in coins:  
        while amount >= coin:  
            amount -= coin  
            result.append(coin)  
    return result if amount == 0 else []  # 无法找零时返回空列表  

# 示例输入  
coins = [1, 5, 10, 25]  
amount = 63  
print(coin_change(coins, amount))  # 输出: [25, 25, 10, 1, 1, 1]

解释：算法优先使用最大面额的硬币，逐步减少剩余金额。此例中，最优解是使用最少数量的硬币（6枚）。

实际应用案例

贪心算法在以下场景中广泛应用：

• 霍夫曼编码：用于数据压缩，优先合并频率最低的字符。
• 最小生成树（如Prim和Kruskal算法）。
• 任务调度：选择结束时间最早的任务以最大化完成数量。

任务调度问题示例

给定一组任务的开始和结束时间，求最多能完成多少个不重叠的任务。

  
def max_tasks(tasks):  
    tasks.sort(key=lambda x: x[1])  # 按结束时间排序  
    count, end = 0, -float('inf')  
    for s, e in tasks:  
        if s >= end:  
            count += 1  
            end = e  
    return count  

tasks = [(1, 3), (2, 5), (4, 7), (6, 9)]  
print(max_tasks(tasks))  # 输出: 3（选择 (1,3), (4,7), (6,9)）

贪心算法的局限性

贪心算法不一定能得到全局最优解，例如：

• 0-1背包问题：贪心选择单位价值最高的物品可能失败。
• 旅行商问题：局部最优路径不一定构成全局最短路径。

与其他算法对比

贪心算法 vs 动态规划

特性	贪心算法	动态规划
决策依据	当前局部最优	所有子问题解
回溯	无	需要
时间复杂度	通常更低	较高
适用问题	满足贪心性质的问题	重叠子问题结构

数学基础

贪心算法的正确性常通过数学归纳法或交换论证证明。例如，对于任务调度问题，可通过反证法证明“选择最早结束任务”的策略最优。

总结

贪心算法以其高效性在特定问题中表现优异，但需注意其适用条件。理解问题是否具有贪心性质是应用该算法的关键。

graph TD A[问题分解] --> B[求解子问题局部最优] B --> C[合并为全局解] C --> D{是否满足终止条件?} D -->|是| E[输出结果] D -->|否| B