编辑“︁贪心算法原理”︁（章节）

= 贪心算法原理 =

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致全局最优解的算法策略。贪心算法并不保证总能得到最优解，但在许多问题中确实能产生最优解或接近最优解的结果。

== 基本概念 ==
贪心算法的核心思想是“局部最优导致全局最优”。它通过一系列局部最优选择来构造问题的解，而不回溯或重新考虑之前的选择。贪心算法通常用于解决最优化问题，如最小生成树、哈夫曼编码、任务调度等。

贪心算法的特点：
* '''无后效性'''：一旦做出选择，就不再改变。
* '''贪心选择性质'''：每一步的局部最优选择能导致全局最优解。
* '''最优子结构'''：问题的最优解包含其子问题的最优解。

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

== 代码示例：找零问题 ==
贪心算法的一个经典应用是'''找零问题'''：给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数。

<syntaxhighlight lang="python">
def coin_change(coins, amount):
    coins.sort(reverse=True)  # 按面额从大到小排序
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1  # 如果无法正好找零，返回-1

# 示例
coins = [1, 5, 10, 25]
amount = 36
print(coin_change(coins, amount))  # 输出：3（25 + 10 + 1）
</syntaxhighlight>

'''输入'''：硬币面额列表 <code>[1, 5, 10, 25]</code>，总金额 <code>36</code>  
'''输出'''：最少硬币数为 <code>3</code>（25 + 10 + 1）

== 实际案例：任务调度 ==
贪心算法常用于任务调度问题，例如：给定一组任务的开始时间和结束时间，如何安排任务以使完成的任务数最多？

<syntaxhighlight lang="python">
def task_scheduling(tasks):
    tasks.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = []
    last_end = -float('inf')
    for start, end in tasks:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

# 示例
tasks = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]
print(task_scheduling(tasks))  # 输出：[(1, 3), (3, 6), (6, 8)]
</syntaxhighlight>

'''输入'''：任务列表 <code>[(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]</code>  
'''输出'''：最多可安排的任务为 <code>[(1, 3), (3, 6), (6, 8)]</code>

== 贪心算法的局限性 ==
贪心算法并不适用于所有问题。例如，在'''0-1背包问题'''中，贪心算法无法保证得到最优解。以下是一个反例：
* 物品：[(价值: 60, 重量: 10), (价值: 100, 重量: 20), (价值: 120, 重量: 30)]
* 背包容量：50

贪心策略（按价值/重量比排序）会选择物品1和物品2，总价值160，但最优解是物品2和物品3，总价值220。

== 贪心算法的应用场景 ==
贪心算法适用于以下问题：
* '''最小生成树'''（Prim算法、Kruskal算法）
* '''哈夫曼编码'''
* '''Dijkstra最短路径算法'''
* '''活动选择问题'''

== 贪心算法与动态规划的区别 ==
贪心算法和动态规划（DP）都用于最优化问题，但有以下区别：
* 贪心算法：局部最优选择，无回溯。
* 动态规划：保存子问题的解，通过组合子问题的解得到全局最优解。

== 总结 ==
贪心算法是一种简单高效的算法策略，适用于具有贪心选择性质和最优子结构的问题。尽管它不保证所有问题的最优解，但在许多实际应用中表现优异。理解贪心算法的原理和适用场景是掌握算法设计的重要一步。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:贪心算法]]