编辑“︁贪心算法”︁

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

== 核心思想 ==  
贪心算法的核心是“局部最优导致全局最优”。它不回溯之前的决策，也不考虑未来的可能性，仅基于当前信息做出选择。其关键特性包括：  
* '''贪心选择性质'''：每一步的局部最优选择能构成全局最优解。  
* '''最优子结构'''：问题的最优解包含其子问题的最优解。  

== 算法步骤 ==  
贪心算法的一般步骤如下：  
# 将问题分解为多个子问题。  
# 对每个子问题求解局部最优解。  
# 将局部最优解合并为全局解。  

== 代码示例 ==  
以下是一个经典的贪心算法问题——'''找零钱问题'''的Python实现：  
<syntaxhighlight lang="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]  
</syntaxhighlight>  
'''解释'''：算法优先使用最大面额的硬币，逐步减少剩余金额。此例中，最优解是使用最少数量的硬币（6枚）。  

== 实际应用案例 ==  
贪心算法在以下场景中广泛应用：  
* '''霍夫曼编码'''：用于数据压缩，优先合并频率最低的字符。  
* '''最小生成树'''（如Prim和Kruskal算法）。  
* '''任务调度'''：选择结束时间最早的任务以最大化完成数量。  

=== 任务调度问题示例 ===  
给定一组任务的开始和结束时间，求最多能完成多少个不重叠的任务。  
<syntaxhighlight lang="python">  
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)）  
</syntaxhighlight>  

== 贪心算法的局限性 ==  
贪心算法不一定能得到全局最优解，例如：  
* '''0-1背包问题'''：贪心选择单位价值最高的物品可能失败。  
* '''旅行商问题'''：局部最优路径不一定构成全局最短路径。  

== 与其他算法对比 ==  
{| class="wikitable"  
|+ 贪心算法 vs 动态规划  
! 特性 !! 贪心算法 !! 动态规划  
|-  
| 决策依据 || 当前局部最优 || 所有子问题解  
|-  
| 回溯 || 无 || 需要  
|-  
| 时间复杂度 || 通常更低 || 较高  
|-  
| 适用问题 || 满足贪心性质的问题 || 重叠子问题结构  
|}  

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

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

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]