贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即局部最优）的决策，从而希望导致全局最优解的算法策略。它通常用于解决最优化问题，如最短路径、任务调度、背包问题等。贪心算法不保证总能得到全局最优解，但在某些问题中能高效地给出近似最优解或精确解。
基本思想
贪心算法的核心思想是：
- 局部最优选择：在每一步选择中，选取对当前问题最有利的选项，不考虑后续步骤的影响。
- 无后效性：当前的选择不会影响后续子问题的结构，即后续步骤的求解不依赖之前的选择。
- 不可回溯：一旦做出选择，就不能回退或重新选择。
贪心算法的有效性依赖于问题的贪心选择性质（Greedy Choice Property）和最优子结构（Optimal Substructure）。
贪心选择性质
通过局部最优选择能够达到全局最优解。
最优子结构
问题的最优解包含其子问题的最优解。
算法步骤
贪心算法通常遵循以下步骤：
- 将问题分解为若干子问题。
- 对每个子问题求解局部最优解。
- 将局部最优解合并为全局解。
示例代码
以下是贪心算法的经典示例：找零钱问题。假设硬币面值为1、5、10、25，要求用最少数量的硬币凑出给定金额。
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]
输入: 63（需要凑出的金额） 输出: [25, 25, 10, 1, 1, 1]（使用的硬币） 解释: 算法优先选择最大面额的硬币，直到无法继续选择，再转向次大面额。
实际应用案例
贪心算法在以下场景中广泛应用：
1. 霍夫曼编码（Huffman Coding）
用于数据压缩，通过贪心策略构造最优前缀码。
2. 最小生成树（Prim/Kruskal算法）
选择权重最小的边来构建生成树。
3. 任务调度问题
如会议室安排，选择最早结束的任务以最大化安排数量。
贪心算法的局限性
贪心算法并非万能，以下情况可能失效：
- 问题不具备贪心选择性质（如0-1背包问题）。
- 需要全局回溯或动态规划才能解决的情况。
与其他算法的对比
| 算法类型 | 特点 | 适用场景 |
|---|---|---|
| 贪心算法 | 局部最优，不回溯 | 最短路径、任务调度 |
| 动态规划 | 记忆化，全局最优 | 背包问题、最长子序列 |
| 分治算法 | 递归分解，合并解 | 归并排序、快速排序 |
复杂度分析
贪心算法的时间复杂度通常较低，例如：
- 找零钱问题：O(n)，其中n是硬币种类数。
- 任务调度问题：O(n log n)，因需要排序。
练习题目
1. 给定一组区间，选择不重叠区间的最大数量（区间调度问题）。 2. 用最少数量的箭头引爆气球（LeetCode 452）。
总结
贪心算法通过局部最优选择逼近全局最优解，适合解决特定类型的最优化问题。理解其适用条件和局限性是掌握该算法的关键。