贪婪法（Greedy Algorithm），又称贪心算法，是一种在每一步选择中都采取当前状态下最优（即最有利）的选择-CSDN博客

本文链接：https://blog.csdn.net/blog_programb/article/details/148155374

贪婪法（Greedy Algorithm），又称贪心算法，是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望最终结果是全局最优解的算法。

基本思想

贪婪法的核心在于局部最优选择。它从问题的初始解出发，逐步进行选择，每次选择都满足局部优化的条件。如果某个候选对象加入当前解中仍可行，则将其加入；否则丢弃。通过这种方式，逐步构建问题的解。

适用条件

贪婪法适用于具有贪心选择性质和最优子结构的问题。贪心选择性质是指全局最优解可以通过局部最优解获得，而最优子结构是指原问题的最优解包含子问题的最优解。

优点

简单直观：逻辑简单，容易理解和实现。
效率高：通常计算复杂度较低，适合快速求解。

缺点

局限性：只能保证局部最优，不一定能得到全局最优解。
适用范围有限：并非所有问题都适合用贪婪法解决。

经典应用

活动选择问题：选择最多的不重叠活动。
最小生成树问题：如Prim和Kruskal算法。
霍夫曼编码：用于数据压缩。

示例

在旅行推销员问题中，每次选择最近的城市作为下一步目标，这就是一种贪婪策略。

贪婪法（贪心算法）概述

贪婪法（Greedy Algorithm） 是一种在每一步选择中都采取当前状态下最优（即最有利）策略的算法设计方法，其核心思想是“短视”地追求局部最优解，从而希望最终得到全局最优解。尽管贪心算法不一定总能获得全局最优解（需具体问题具体分析），但因其简单高效，常用于求解最优化问题。

贪婪法的基本要素

贪心选择性质
算法在每一步的局部最优选择都能推动整体向全局最优解靠近，即全局最优解可通过一系列局部最优选择达到。
例如：在“活动选择问题”中，每次选择结束时间最早的活动，最终可得到最多活动数的全局解。
最优子结构性质
问题的最优解包含其子问题的最优解，即整体问题的最优解可分解为子问题的最优解。
例如：最短路径问题中，若从A到C的最短路径经过B，则A到B和B到C的路径也必为最短路径。

贪婪法的解题步骤

确定问题的最优子结构：分析问题是否具有可分解的子问题，且子问题的最优解可组合为原问题的最优解。
设计贪心策略：定义每一步的局部最优选择规则（如“选择当前最小/最大元素”“选择代价最小的选项”等）。
证明贪心策略的正确性：通过数学归纳法或反证法证明局部最优选择能导向全局最优解（这一步是关键，若无法证明，则算法可能不成立）。
实现算法：根据贪心策略编写代码，通常时间复杂度较低（如O(n log n)或O(n)）。

经典应用场景

以下是贪婪法在不同领域的典型应用，附具体案例说明：

1. 背包问题（部分背包问题）

问题描述：有一个容量为 ( W ) 的背包，给定 ( n ) 个物品，每个物品有重量 ( w_i ) 和价值 ( v_i )，允许分割物品。求如何装入物品使总价值最大。
贪心策略：按单位重量价值（( v_i/w_i )）从高到低排序，优先装入单位价值高的物品，直至背包装满。
正确性证明：由于允许分割，局部最优选择（单位价值最高）可累加成全局最优解。

2. 最小生成树（Kruskal算法/Prim算法）

Kruskal算法：按边权从小到大排序，依次选择不构成环的边，直至生成树包含所有顶点。
Prim算法：从任意顶点出发，每次选择与当前树相连的最小权边，扩展生成树。
贪心策略：两者均通过局部最小边权选择，逐步构建全局最优的最小生成树。

3. 最短路径（Dijkstra算法）

问题描述：在带权有向图中，求从起点到其他所有顶点的最短路径。
贪心策略：维护当前已知的最短路径，每次选择距离起点最近的顶点，更新其邻接顶点的路径长度。
适用条件：图中边权非负，否则需使用Bellman-Ford算法。

4. 区间调度问题（活动选择）

问题描述：有若干活动，每个活动有起始时间和结束时间，求最多可安排的互不冲突的活动数。
贪心策略：按结束时间升序排序，每次选择结束时间最早且不与已选活动冲突的活动。
正确性证明：最早结束的活动为后续腾出最多时间，从而最大化活动数。

贪婪法 vs. 动态规划

对比维度	贪婪法	动态规划
决策方式	局部最优（当前步骤直接选最优解）	全局最优（需遍历所有子问题组合）
子问题依赖	无后效性（不依赖后续子问题）	依赖所有子问题（需存储中间结果）
时间复杂度	通常较低（如排序+线性遍历）	较高（如O(n²)或O(n×W)）
适用场景	需满足贪心选择性质和最优子结构	需满足最优子结构，但不要求贪心选择

贪婪法的局限性与注意事项

不一定得到全局最优解：
若问题不满足贪心选择性质，局部最优可能导致全局次优。例如“0-1背包问题”（不允许分割物品）中，贪心算法可能无法得到最优解，需用动态规划。
正确性证明至关重要：
设计贪心策略后需严格证明其有效性，否则算法可能失效。例如在“硬币找零问题”中，只有特定币值体系（如美国硬币）下贪心算法才正确，若币值为{1, 3, 4}，找6元时贪心（4+1+1）非最优（3+3）。
贪心策略的多样性：
同一问题可能有多种贪心策略，需选择能导向全局最优的策略。例如霍夫曼编码中，选择频率最小的两个节点合并，可生成最优前缀码。

代码示例：活动选择问题

def activity_selection(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    selected = []
    last_end = -1
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

# 示例输入：活动列表（起始时间，结束时间）
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print("选择的活动：", activity_selection(activities))
# 输出：[(1, 4), (5, 7), (8, 11), (12, 16)]