编辑“︁贪心算法”︁

{{DISPLAYTITLE:贪心算法}}  
'''贪心算法'''（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即局部最优）的决策，从而希望导致全局最优解的算法策略。它通常用于解决最优化问题，如最短路径、任务调度、背包问题等。贪心算法不保证总能得到全局最优解，但在某些问题中能高效地给出近似最优解或精确解。

== 基本思想 ==  
贪心算法的核心思想是：  
# '''局部最优选择'''：在每一步选择中，选取对当前问题最有利的选项，不考虑后续步骤的影响。  
# '''无后效性'''：当前的选择不会影响后续子问题的结构，即后续步骤的求解不依赖之前的选择。  
# '''不可回溯'''：一旦做出选择，就不能回退或重新选择。

贪心算法的有效性依赖于问题的'''贪心选择性质'''（Greedy Choice Property）和'''最优子结构'''（Optimal Substructure）。  

=== 贪心选择性质 ===  
通过局部最优选择能够达到全局最优解。  

=== 最优子结构 ===  
问题的最优解包含其子问题的最优解。  

== 算法步骤 ==  
贪心算法通常遵循以下步骤：  
# 将问题分解为若干子问题。  
# 对每个子问题求解局部最优解。  
# 将局部最优解合并为全局解。  

== 示例代码 ==  
以下是贪心算法的经典示例：'''找零钱问题'''。假设硬币面值为1、5、10、25，要求用最少数量的硬币凑出给定金额。  

<syntaxhighlight lang="python">  
def greedy_coin_change(amount, coins=[25, 10, 5, 1]):  
    coins.sort(reverse=True)  # 从大到小排序  
    result = []  
    for coin in coins:  
        while amount >= coin:  
            amount -= coin  
            result.append(coin)  
    return result  

# 示例  
print(greedy_coin_change(63))  # 输出: [25, 25, 10, 1, 1, 1]  
</syntaxhighlight>  

'''输入''': 63（需要凑出的金额）  
'''输出''': [25, 25, 10, 1, 1, 1]（使用的硬币）  
'''解释''': 算法优先选择最大面额的硬币，直到无法继续选择，再转向次大面额。  

== 实际应用案例 ==  
贪心算法在以下场景中广泛应用：  
=== 1. 霍夫曼编码（Huffman Coding） ===  
用于数据压缩，通过贪心策略构造最优前缀码。  

=== 2. 最小生成树（Prim/Kruskal算法） ===  
选择权重最小的边来构建生成树。  

=== 3. 任务调度问题 ===  
如会议室安排，选择最早结束的任务以最大化安排数量。  

== 贪心算法的局限性 ==  
贪心算法并非万能，以下情况可能失效：  
* 问题不具备贪心选择性质（如0-1背包问题）。  
* 需要全局回溯或动态规划才能解决的情况。  

== 与其他算法的对比 ==  
{| class="wikitable"  
|+ 贪心算法 vs 动态规划 vs 分治算法  
|-  
! 算法类型 !! 特点 !! 适用场景  
|-  
| '''贪心算法''' || 局部最优，不回溯 || 最短路径、任务调度  
|-  
| '''动态规划''' || 记忆化，全局最优 || 背包问题、最长子序列  
|-  
| '''分治算法''' || 递归分解，合并解 || 归并排序、快速排序  
|}  

== 复杂度分析 ==  
贪心算法的时间复杂度通常较低，例如：  
* 找零钱问题：O(n)，其中n是硬币种类数。  
* 任务调度问题：O(n log n)，因需要排序。  

== 练习题目 ==  
1. 给定一组区间，选择不重叠区间的最大数量（[[区间调度问题]]）。  
2. 用最少数量的箭头引爆气球（[[LeetCode 452]]）。  

== 总结 ==  
贪心算法通过局部最优选择逼近全局最优解，适合解决特定类型的最优化问题。理解其适用条件和局限性是掌握该算法的关键。  

<mermaid>  
graph TD  
    A[问题分解] --> B[局部最优选择]  
    B --> C[合并解]  
    C --> D{是否满足全局最优?}  
    D -->|是| E[输出结果]  
    D -->|否| F[尝试其他策略]  
</mermaid>

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:算法基础]]