Okay, here is a detailed article covering Greedy Algorithms, aiming for approximately 5000 words.

---

一文读懂贪心算法：原理、步骤与实例

引言：生活中的“贪心”智慧

想象一下，你在超市排队结账，面前有几条队伍。你通常会怎么选？很可能，你会选择当前看起来人最少的队伍，或者预估处理速度最快的收银员所在的队伍。又或者，当你需要用最少数量的硬币凑出某个金额（比如 8 毛 7 分），你很可能会先拿出最大面值的硬币（5 毛），然后是次大面值的（2 毛），接着是（1 毛），最后是（5 分）和（2 分）。

这些日常决策背后，其实蕴含着一种重要的算法思想——贪心算法（Greedy Algorithm）。贪心算法的核心思想是：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法所做出的仅是在某种意义上的局部最优解。贪心算法期望通过每个阶段的局部最优选择，最终达到全局最优解。

然而，生活经验告诉我们，“贪心”并不总是带来最好的结果。选择最短的队伍可能因为前面的人购买了大量商品而变得缓慢；找零时如果硬币面值特殊（例如没有 5 毛，只有 1 毛、3 毛、4 毛），优先选最大面额（4 毛）凑 6 毛钱（4+1+1=3枚）可能不如两枚 3 毛（3+3=2枚）更优。

这正是贪心算法的魅力与挑战所在：它简单、高效，易于实现，在许多问题上能给出最优解，但它并不适用于所有问题。关键在于，我们需要理解贪心算法的工作原理，掌握其适用条件，并学会证明其正确性。

本文将带你深入探索贪心算法的世界，从基本原理到实施步骤，再通过一系列经典实例，让你真正“一文读懂”贪心算法，掌握其精髓，并能在实际问题中灵活运用或判断其适用性。

一、贪心算法的核心原理

贪心算法的运作基于一个重要的假设：局部最优选择能够导向全局最优解。为了让这个假设成立，一个问题通常需要满足两个关键性质：

1. 贪心选择性质 (Greedy Choice Property)

这是贪心算法能够成立的最核心的性质。它指的是：所求问题的整体最优解，可以通过一系列局部最优的选择（即贪心选择）来达到。

更具体地说，当我们面临一个选择时，我们做出的那个“当前看起来最好”的选择，必须是构成问题某个全局最优解的一部分，而无需考虑后续的选择。这个选择一旦做出，就不会在后续步骤中被撤销或更改。

如何理解？
假设我们有一个问题，需要做出一系列决策 D1, D2, …, Dn。贪心选择性质意味着：
– 我们可以根据某种“贪心”标准，直接确定第一个决策 D1。
– 存在至少一个全局最优解 S = {D1, D’2, …, D’k}，它包含了我们做出的第一个贪心选择 D1。

这个性质是贪心算法与动态规划等其他算法（如动态规划需要考虑所有子问题的最优解来构造当前问题的最优解）的关键区别。贪心算法“目光短浅”，只看眼前，做出选择后就直接缩小问题规模，不再回头看。

验证贪心选择性质的重要性：
在使用贪心算法之前，必须证明（或确信）问题具有贪心选择性质。如果凭直觉或猜测应用贪心策略，很可能得到错误的或次优的解。后面我们会看到反例，例如 0-1 背包问题就不满足贪心选择性质。

2. 最优子结构性质 (Optimal Substructure Property)

这个性质与动态规划中的最优子结构类似，但应用于贪心算法时有其特殊含义。它指的是：一个问题的最优解包含了其子问题的最优解。

在贪心算法的语境下，这意味着：当我们做出了一个贪心选择后，原问题就简化为了一个规模更小、结构类似的子问题。如果原问题具有最优子结构性质，那么这个子问题的最优解，加上我们之前做出的贪心选择，就构成了原问题的一个最优解。

如何理解？
假设问题 P 的一个最优解 S 包含了一个贪心选择 G。如果我们将 G 从 S 中移除，并考虑因做出选择 G 而产生的子问题 P’，那么 S 中剩余的部分 S’ 必须是子问题 P’ 的一个最优解。

与动态规划的区别：
虽然动态规划也依赖最优子结构，但它通常会考察所有相关的子问题，并从中选择最优的来构建更大问题的解。而贪心算法在做出贪心选择后，只关心一个由该选择导出的子问题，并假定继续对这个子问题使用贪心策略也能得到其最优解。

总结：
一个问题能用贪心算法求解，必须同时满足贪心选择性质和最优子结构性质。
– 贪心选择性质保证了我们当前做出的局部最优选择的“正确性”（它是某个全局最优解的一部分）。
– 最优子结构性质保证了在做出贪心选择后，问题可以被分解，并且剩余的子问题仍然可以通过（通常是相同的）贪心策略来最优地解决。

只有这两个性质同时成立，一步步的局部最优选择才能最终累积成全局最优解。

二、贪心算法的设计步骤

设计一个贪心算法通常遵循以下步骤：

1. 问题建模与理解：

   • 将实际问题抽象成一个清晰定义的数学模型或优化问题。明确输入是什么，输出（目标）是什么，以及求解的约束条件。
   • 例如，活动选择问题：输入是一系列活动的开始和结束时间，输出是最大数量的不冲突活动集合，约束是选出的活动时间上不能重叠。

2. 寻找贪心策略（识别贪心选择性质）：

   • 这是最关键也往往是最困难的一步。需要确定在每一步应该基于什么标准（“贪心”标准）来做出选择。
   • 常见的贪心标准可能包括：选择最小的/最大的元素、选择最早开始/结束的、选择最高性价比的、选择最短/最长的等等。
   • 可能需要尝试多种贪心策略，并通过分析或小规模实例来判断哪种策略最有希望。
   • 例如，在活动选择问题中，可以考虑的策略有：选择持续时间最短的活动？选择开始时间最早的活动？选择结束时间最早的活动？

3. 证明贪心选择的正确性（证明贪心选择性质）：

   • 一旦确定了贪心策略，必须严格证明该策略满足贪心选择性质。即证明：按照此策略做出的第一个选择，必然包含在问题的某个最优解中。
   • 常用的证明方法是交换论证法 (Exchange Argument)：
     a. 假设存在一个最优解 OPT，它没有采用贪心算法做出的第一个选择 g。
     b. 证明可以将 OPT 中的某个元素替换为 g，得到一个新的解 OPT'，并且 OPT' 至少和 OPT 一样优（通常是同样优或更优），且 OPT' 包含了贪心选择 g。
     c. 这就说明，总存在一个最优解是以贪心选择开始的。
   • 这一步是确保贪心算法正确性的基石。如果无法证明，那么该贪心策略很可能是错误的。

4. 证明最优子结构性质：

   • 证明当做出了一个贪心选择后，原问题简化为的子问题仍然具有最优解，并且原问题的最优解可以通过贪心选择和子问题的最优解组合而成。
   • 通常这一步比较直观：如果全局最优解包含第一个贪心选择 g，那么去掉 g 和与之相关的部分后，剩下的解必须是剩余子问题的最优解。否则，如果子问题有更优的解，替换掉原解中对应部分，就能得到比原最优解更好的解，产生矛盾。

5. 算法设计与实现：

   • 基于确定的贪心策略，设计具体的算法步骤。通常是一个迭代或递归的过程：
     a. 根据贪心标准选择一个元素/决策。
     b. 将该选择加入解集。
     c. 移除已选择的元素和与之冲突的元素，更新问题状态（缩小问题规模）。
     d. 重复以上步骤，直到问题被完全解决或无法再做出选择。
   • 选择合适的数据结构（如排序数组、优先队列/堆）来高效地实现贪心选择和问题状态更新。

6. 复杂度分析：

   • 分析算法的时间复杂度和空间复杂度。贪心算法通常效率较高，时间复杂度往往取决于排序或使用优先队列等操作。

下面，我们将通过几个经典的例子来具体演示这些步骤。

三、经典贪心算法实例解析

实例一：零钱兑换问题 (Change-Making Problem) – 特定情况

问题描述：
假设有面值为 v1, v2, ..., vk 的硬币，数量无限。需要用最少数量的硬币凑出给定的总金额 A。

特殊情况：规范币制系统
我们日常使用的币制系统（如人民币 1元, 5角, 1角, 5分, 2分, 1分；美元 100, 50, 25, 10, 5, 1）通常是“规范”的，对于这种系统，贪心策略有效。

1. 问题建模：
– 输入：硬币面值集合 V = {v1, v2, ..., vk} (通常已降序排列，v1 > v2 > ... > vk)，目标金额 A。
– 输出：一个表示各种硬币数量的集合 N = {n1, n2, ..., nk}，使得 sum(ni * vi) = A 且 sum(ni) 最小。

2. 贪心策略：
在每一步，选择当前能使用的最大面值的硬币，且该面值不超过剩余需要凑的金额。重复此过程，直到凑足总金额 A。

3. 证明贪心选择正确性 (针对规范币制系统，以人民币为例)：
人民币币制 {100, 50, 20, 10, 5, 1, 0.5, 0.1, 0.05, 0.02, 0.01} 元。
假设需要凑金额 A。贪心选择是先用尽可能多的最大面值 v_max <= A 的硬币。
我们用交换论证法证明：任何最优解都可以被调整为包含这个贪心选择，而不增加硬币总数。
设 OPT 是一个最优解。设贪心选择的第一步是使用 k 枚面值为 v_max 的硬币（k 是能使用的最大数量）。
如果 OPT 中 v_max 硬币的数量 k_opt 等于 k，则满足。
如果 k_opt < k，那么 OPT 必须用更小面值的硬币来凑足 k * v_max - k_opt * v_max 这部分金额。
对于规范币制系统，有一个性质：任何大于等于某个面额 v_i 的金额，如果用小于 v_i 的面额组合来支付，其所需硬币数量必然大于等于用 v_i 支付（如果可能）的数量。例如，凑 5 毛钱，用 5 个 1 毛肯定不如用 1 个 5 毛。
因此，在 OPT 中，用于凑 (k - k_opt) * v_max 这部分金额的小面值硬币，其总数必然不会少于 (k - k_opt) 枚。我们可以将这些小面值硬币替换为 (k - k_opt) 枚 v_max 硬币，总金额不变，但硬币数量可能减少或不变。这样我们就得到了一个新的最优解（或同样优的解），它包含了贪心选择（使用了 k 枚 v_max 硬币）。
所以，贪心选择性质成立。

4. 证明最优子结构性质：
假设凑金额 A 的最优解是先用 k 枚 v_max 硬币，然后用最优的方式凑剩余金额 A' = A - k * v_max。如果凑 A' 的方式不是最优的（用了 m 枚硬币，但存在只需 m' < m 枚硬币的方式），那么用 k 枚 v_max 加上这 m' 枚硬币就能凑出 A，总硬币数为 k + m' < k + m，这与原解是最优的矛盾。
因此，最优子结构性质成立。

5. 算法实现：

“`python
def greedy_change(coins, amount):
“””
使用贪心算法计算规范币制下的最少硬币数 (硬币面值需降序排列)
“””
coins.sort(reverse=True) # 确保面值降序
num_coins = 0
result_coins = {} # 记录每种面值用了多少

for coin in coins:
    if amount == 0:
        break
    if coin <= amount:
        count = amount // coin
        num_coins += count
        amount -= count * coin
        result_coins[coin] = count

if amount == 0:
    return num_coins, result_coins
else:
    # 如果是规范币制，这里应该不会发生
    # 但对于非规范币制，贪心可能无法凑齐
    return -1, {}

示例：人民币找零 8.87 元

coins_rmb = [100, 50, 20, 10, 5, 1, 0.5, 0.1, 0.05, 0.02, 0.01]
amount_rmb = 8.87
count, change = greedy_change(coins_rmb, amount_rmb)
print(f”凑 {amount_rmb} 元最少需要 {count} 枚硬币: {change}”)

输出: 凑 8.87 元最少需要 8 枚硬币: {5: 1, 1: 3, 0.5: 1, 0.1: 3, 0.05: 1, 0.02: 1} (可能因浮点数精度略有差异，实际应用应使用整数分)

验证：51 + 13 + 0.51 + 0.13 + 0.051 + 0.021 = 5 + 3 + 0.5 + 0.3 + 0.05 + 0.02 = 8.87. 数量 1+3+1+3+1+1 = 10 (啊哈，上面的手动计算错了，程序是对的，5+1+1+0.5+0.13+0.05+0.02 = 7+0.5+0.3+0.05+0.02=7.87, 需要8.87，应该是 51 + 13 + 0.51 + 0.13 + 0.051 + 0.02*1 = 5+3+0.5+0.3+0.05+0.02 = 8.87. 数量 1+3+1+3+1+1 = 10. 我的例子计算错了，重新算下手动找零：8.87 -> 5元(1枚,剩3.87) -> 1元(3枚,剩0.87) -> 0.5元(1枚,剩0.37) -> 0.1元(3枚,剩0.07) -> 0.05元(1枚,剩0.02) -> 0.02元(1枚,剩0). 总共 1+3+1+3+1+1 = 10枚. 程序是对的.)

“`

6. 复杂度分析：
– 时间复杂度：如果硬币面值已排序，算法需要遍历一次面值列表，每次做除法和减法。设面值有 k 种，则为 O(k)。如果需要排序，则为 O(k log k)。
– 空间复杂度：O(k) 或 O(1)，取决于是否需要存储结果中各种硬币的数量。

重要提示：贪心算法并非万能
对于非规范币制系统，贪心算法可能失败。
例子：硬币面值 V = {1, 3, 4}，目标金额 A = 6。
– 贪心策略：
– 选 4 (剩余 2)
– 选 1 (剩余 1)
– 选 1 (剩余 0)
– 总共 3 枚硬币 (4, 1, 1)。
– 最优解：
– 选 3 (剩余 3)
– 选 3 (剩余 0)
– 总共 2 枚硬币 (3, 3)。
贪心失败！因为选择 4 这个局部最优选择，并未导向全局最优。这种情况下，通常需要使用动态规划。

实例二：活动选择问题 (Activity Selection Problem)

问题描述：
有 n 个活动，每个活动 i 都有一个开始时间 s_i 和结束时间 f_i (s_i < f_i)。这些活动竞争使用同一个资源（如会议室），任何时刻该资源只能被一个活动占用。目标是选择一个最大数量的、互相兼容（时间上不重叠）的活动集合。

1. 问题建模：
– 输入：n 个活动，每个活动表示为 (s_i, f_i)。
– 输出：一个活动子集 S，使得 S 中任意两个活动 i 和 j 都不重叠（即 s_i >= f_j 或 s_j >= f_i），并且 |S| 最大。

2. 寻找贪心策略：
可以考虑多种贪心标准：
– a. 选择持续时间最短的活动？ 反例：一个很短的活动可能正好卡在两个较长但不冲突的活动之间，选了它就无法选那两个。例如：(0,6), (6,12), (5,7)。最短的是(5,7)，选了它就不能选(0,6)和(6,12)。但最优解是(0,6)和(6,12)，共2个。
– b. 选择开始时间最早的活动？ 反例：一个开始很早但持续时间很长的活动，可能会阻塞掉后面很多短活动。例如：(0, 10), (1, 3), (4, 6), (7, 9)。最早开始是(0,10)，选了它就没了。但最优解是(1,3), (4,6), (7,9)，共3个。
– c. 选择结束时间最早的活动？ 这个策略看起来更有希望。选择结束最早的活动，似乎能给后续活动留出更多的时间。
– d. 选择冲突最少的活动？ 计算冲突比较复杂，可能不是高效的贪心策略。

我们重点考察策略 c：总是选择当前所有可选活动中，结束时间最早的那个活动。

3. 证明贪心选择正确性（策略 c）：
– 贪心选择： 从所有活动中，选择结束时间 f_k 最早的活动 k。
– 证明（交换论证法）：
a. 假设存在一个最优解 OPT。设 OPT 中第一个结束的活动是 j。设贪心选择的第一个活动（即所有活动中结束时间最早的）是 k。
b. 根据贪心选择的定义，f_k <= f_j。
c. 比较活动 k 和 j：
– 如果 k 就是 j，那么 OPT 已经包含了第一个贪心选择，性质成立。
– 如果 k 不是 j，由于 f_k <= f_j，且 j 是 OPT 中第一个结束的活动，那么 k 必然与 OPT 中除了 j 之外的其他活动都不冲突（因为那些活动开始时间都晚于 f_j，也就晚于 f_k）。
d. 我们可以构造一个新的活动集合 OPT' = (OPT - {j}) U {k}。即将 OPT 中的 j 替换为 k。
e. OPT' 中的活动数量与 OPT 相同 (|OPT'| = |OPT|)。
f. OPT' 中的活动也是互相兼容的：k 与 OPT - {j} 中的活动不冲突，而 OPT - {j} 内部本来就是兼容的。
g. 因此，OPT' 也是一个最优解，并且它包含了贪心选择的第一个活动 k。
h. 这证明了，总存在一个最优解是以“选择结束时间最早的活动”这个贪心选择开始的。贪心选择性质成立。

4. 证明最优子结构性质：
– 当我们选择了第一个活动 k（结束时间最早）后，原问题就变成了：在所有开始时间晚于等于 f_k 的活动中，选择最大数量的兼容活动。
– 设原问题的最优解 S 包含了活动 k。令 S' = S - {k}。S' 必然是子问题（在 s_i >= f_k 的活动中找最优解）的一个最优解。
– 如果 S' 不是子问题的最优解，那么子问题存在一个更优的解 S'' (|S''| > |S'|)。那么 S* = {k} U S'' 将是原问题的一个解，且 |S*| = 1 + |S''| > 1 + |S'| = |S|。这与 S 是原问题的最优解矛盾。
– 因此，最优子结构性质成立。

5. 算法实现：

“`python
def activity_selection(activities):
“””
使用贪心算法解决活动选择问题
activities: 列表，每个元素是 (start_time, end_time)
“””
if not activities:
return []

# 1. 按结束时间升序排序
activities.sort(key=lambda x: x[1])

selected_activities = []
# 2. 选择第一个活动 (结束时间最早的)
selected_activities.append(activities[0])
last_end_time = activities[0][1]

# 3. 遍历剩余活动
for i in range(1, len(activities)):
    current_start_time, current_end_time = activities[i]
    # 如果当前活动的开始时间 >= 上一个选定活动的结束时间
    if current_start_time >= last_end_time:
        selected_activities.append(activities[i])
        last_end_time = current_end_time # 更新最后一个选定活动的结束时间

return selected_activities

示例

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = activity_selection(activities)
print(f”最多可以选择 {len(result)} 个活动: {result}”)

输出: 最多可以选择 4 个活动: [(1, 4), (5, 7), (8, 11), (12, 14)]

或者 [(1, 4), (5, 7), (8, 12), (12, 14)] 取决于排序稳定性，结束时间相同时(8,11)和(8,12)的顺序

重新运行确认一下 [(1, 4), (5, 7), (8, 11), (12, 14)] 是一个标准答案

“`

6. 复杂度分析：
– 时间复杂度：主要在于排序，O(N log N)，其中 N 是活动数量。排序后的遍历是 O(N)。所以总时间复杂度是 O(N log N)。
– 空间复杂度：O(N) 或 O(1)，取决于是否需要存储排序后的副本和结果集。如果原地排序且只返回数量，可以是 O(1)。

实例三：分数背包问题 (Fractional Knapsack Problem)

问题描述：
有一个背包，容量为 W。有 n 种物品，每种物品 i 有一个重量 w_i 和一个价值 v_i。与 0-1 背包不同的是，这里的物品可以分割，即可以只取物品的一部分。目标是选择装入背包的物品（可以是物品的一部分），使得装入物品的总重量不超过背包容量 W，并且总价值最大。

1. 问题建模：
– 输入：背包容量 W，n 个物品，每个物品 i 有 (w_i, v_i)。
– 输出：每种物品取用的比例 x_i (0 <= x_i <= 1)，使得 sum(x_i * w_i) <= W 且 sum(x_i * v_i) 最大。

2. 贪心策略：
既然物品可以分割，我们应该优先装性价比最高的物品。性价比可以用单位重量的价值来衡量，即 p_i = v_i / w_i。
贪心策略：计算所有物品的价值密度 p_i，然后按照 p_i 从高到低（降序）的顺序，依次将物品（或其一部分）装入背包，直到背包被装满或所有物品都考虑完毕。

3. 证明贪心选择正确性：
– 贪心选择： 选择当前剩余物品中，价值密度 p_i 最高的物品 k。
– 证明（交换论证法）：
a. 假设存在一个最优解 OPT，它没有优先尽可能多地装入价值密度最高的物品 k。设 OPT 中装入了 x_k * w_k 的物品 k (x_k < 1 或者 x_k=1 但背包还有容量且有更高密度的物品未装满)。
b. 由于 OPT 是最优解且 sum(x_i * w_i) <= W，如果 OPT 中没有装满背包 (sum < W)，并且还有更高密度的物品 k 没装完，这显然不是最优的，因为可以多装点 k 增加总价值。所以我们只考虑背包被装满 sum = W 的情况，或者所有物品都装了仍未满的情况（此时贪心就是全装，必然最优）。
c. 假设背包已满 sum = W。如果在 OPT 中，物品 k 没有被完全装入 (x_k < 1)，或者 x_k=1 但背包里还装了某个价值密度低于 k 的物品 j (p_j < p_k)，则 OPT 不是最优的。
d. 考虑情况：OPT 中装了 x_j * w_j 的物品 j (x_j > 0, p_j < p_k)，并且物品 k 可能没装满 (x_k < 1) 或已装满但背包里有比它密度低的 j。
e. 我们可以从 OPT 中取出 delta_w 重量（delta_w = min(x_j * w_j, (1 - x_k) * w_k)）的物品 j，腾出空间。
f. 用这 delta_w 的空间装入等重量的物品 k。
g. 价值变化 Delta_V = delta_w * p_k - delta_w * p_j = delta_w * (p_k - p_j)。
h. 因为 p_k > p_j，所以 Delta_V > 0。
i. 这意味着我们通过替换，得到了一个总重量不变（仍为 W）但总价值更高的新解。这与 OPT 是最优解矛盾。
j. 因此，任何最优解都必须优先尽可能多地装入价值密度最高的物品。贪心选择性质成立。

4. 证明最优子结构性质：
– 当我们按照最高价值密度选择物品 k 并装入 min(w_k, W_remaining) 后，问题转化为：用剩余容量 W' = W_remaining - min(w_k, W_remaining)，在剩余的物品中获取最大价值。
– 假设原问题的最优解 S 包含对物品 k 的贪心选择量。令 S' 是 S 中除 k 之外的部分。S' 必须是子问题（用容量 W' 在剩余物品中求最优解）的最优解。证明方式与活动选择类似，使用反证法。如果子问题有更优解，则原问题也能构造出更优解，矛盾。
– 最优子结构性质成立。

5. 算法实现：

“`python
def fractional_knapsack(capacity, items):
“””
使用贪心算法解决分数背包问题
capacity: 背包容量 W
items: 列表，每个元素是 (weight, value)
“””
# 1. 计算每个物品的价值密度并存储 (weight, value, density)
items_with_density = []
for i, (w, v) in enumerate(items):
if w > 0:
density = v / w
items_with_density.append((w, v, density, i)) # 加入原始索引以便追踪
# 可以处理重量为0但价值不为0的物品（如果允许）
elif v > 0:
items_with_density.append((w, v, float(‘inf’), i)) # 密度视为无穷大

# 2. 按价值密度降序排序
items_with_density.sort(key=lambda x: x[2], reverse=True)

total_value = 0.0
knapsack_content = {} # 记录装入的物品及其比例 {index: fraction}

# 3. 遍历排序后的物品
for w, v, density, index in items_with_density:
    if capacity == 0:
        break # 背包已满

    # 如果当前物品可以完全装入
    if w <= capacity:
        total_value += v
        capacity -= w
        knapsack_content[index] = 1.0 # 装入比例为 1
    # 如果当前物品只能部分装入
    else:
        fraction = capacity / w
        total_value += fraction * v
        knapsack_content[index] = fraction
        capacity = 0 # 背包已满

return total_value, knapsack_content

示例

capacity = 50
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)

密度: item 0: 60/10=6; item 1: 100/20=5; item 2: 120/30=4

max_value, content = fractional_knapsack(capacity, items)
print(f”最大价值为: {max_value}”)
print(f”背包内容 (物品索引: 比例): {content}”)

预期步骤：

1. 装物品0 (w=10, v=60, p=6). 剩余容量 50-10=40. 总价值 60. content={0: 1.0}

2. 装物品1 (w=20, v=100, p=5). 剩余容量 40-20=20. 总价值 60+100=160. content={0: 1.0, 1: 1.0}

3. 装物品2 (w=30, v=120, p=4). 剩余容量 20. 只能装 20/30 = 2/3. 价值增加 (2/3)*120=80. 剩余容量 0. 总价值 160+80=240. content={0: 1.0, 1: 1.0, 2: 2/3}

输出: 最大价值为: 240.0

输出: 背包内容 (物品索引: 比例): {0: 1.0, 1: 1.0, 2: 0.6666666666666666}

“`

6. 复杂度分析：
– 时间复杂度：计算密度 O(N)，排序 O(N log N)，遍历 O(N)。总时间复杂度 O(N log N)。
– 空间复杂度：O(N) 用于存储带密度的物品列表和结果。

对比 0-1 背包问题：
值得强调的是，对于 0-1 背包问题（物品不能分割，要么装要么不装），贪心算法（按价值密度）通常无法得到最优解。
例如：容量 W=50，物品 {(10, 60), (20, 100), (30, 120)}。
– 贪心（按密度）：先选物品0 (w=10, v=60, 剩余W=40)，再选物品1 (w=20, v=100, 剩余W=20)，物品2 (w=30) 装不下。总价值 60 + 100 = 160。
– 最优解：选择物品1和物品2 (w=20+30=50, v=100+120=220)。总价值 220。
0-1 背包问题通常需要使用动态规划或回溯法求解。这再次说明了贪心算法的局限性，它依赖于问题的特定结构（如分数背包的可分割性）。

实例四：哈夫曼编码 (Huffman Coding)

问题描述：
给定一组字符及其出现的频率（或权重），找到一种前缀编码 (Prefix Code) 方案，使得编码后的总长度（所有字符的编码长度 * 频率 之和）最小。前缀编码要求任何一个字符的编码不能是另一个字符编码的前缀，这样可以无歧义地解码。

哈夫曼编码是一种用于无损数据压缩的著名贪心算法。

1. 问题建模：
– 输入：字符集合 C，每个字符 c 有一个频率 f(c)。
– 输出：一个二叉树（哈夫曼树），其中叶子节点代表字符，边表示 0 或 1。从根到叶子节点的路径构成该字符的编码。目标是最小化 Sum(f(c) * length(code(c))) 对所有 c in C。

2. 贪心策略：
哈夫曼算法采用自底向上的方法构建编码树：
核心贪心步骤： 在每一步，从当前所有的节点（初始时是所有字符对应的叶子节点，后续包含合并产生的内部节点）中，选择两个频率（权重）最小的节点，将它们合并成一个新的内部节点。这个新节点的频率是其两个子节点频率之和。重复这个过程，直到只剩下一个根节点。

3. 证明贪心选择正确性（简述思路）：
证明哈夫曼编码的贪心策略正确性比较复杂，通常涉及两个引理：
– 引理 1 (兄弟性质)： 在任意一个最优前缀编码对应的二叉树中，存在两个频率最低的字符，它们对应的叶子节点是兄弟关系（拥有共同的父节点），并且位于树的最深层。
– 证明思路（交换论证）：假设频率最低的两个字符 x 和 y 在最优树 T 中不是最深层的兄弟。找到树中最深层的一对兄弟叶子节点 a 和 b。由于 f(x) <= f(a) 且 f(y) <= f(b)，将 x 与 a 交换位置，y 与 b 交换位置，得到新树 T'。可以证明 T' 的总代价不会超过 T 的总代价。因此，总存在一个最优树，使得频率最低的两个字符是位于最深层的兄弟。
– 引理 2 (子问题性质)： 令 x 和 y 是频率最低的两个字符。将它们从字符集 C 中移除，并加入一个新“字符” z，其频率 f(z) = f(x) + f(y)，得到新字符集 C'。如果树 T' 是 C' 的一个最优编码树，那么将 T' 中代表 z 的叶子节点替换为一个以 x 和 y 为子节点的内部节点，得到的树 T 是原字符集 C 的一个最优编码树。
– 证明思路：利用代价的计算公式和 f(z) = f(x) + f(y)，证明原问题代价与子问题代价之间的关系。

这两个引理共同保证了贪心选择（合并频率最小的两个节点）的正确性，并且问题具有最优子结构（解决 C' 的最优编码有助于解决 C 的最优编码）。

4. 算法实现：
通常使用最小优先队列 (Min-Priority Queue)（通常用最小堆实现）来高效地找到并提取两个频率最小的节点。

“`python
import heapq

class HuffmanNode:
def init(self, char, freq):
self.char = char # 字符 (叶子节点) or None (内部节点)
self.freq = freq # 频率
self.left = None
self.right = None

# 为了让 heapq 能比较节点 (按频率比较)
def __lt__(self, other):
    return self.freq < other.freq

def build_huffman_tree(char_freq):
“””构建哈夫曼树”””
priority_queue = [HuffmanNode(char, freq) for char, freq in char_freq.items()]
heapq.heapify(priority_queue) # 构建最小堆 O(N)

while len(priority_queue) > 1:
    # 1. 取出频率最小的两个节点
    left_node = heapq.heappop(priority_queue) # O(log N)
    right_node = heapq.heappop(priority_queue) # O(log N)

    # 2. 合并成新节点
    merged_freq = left_node.freq + right_node.freq
    merged_node = HuffmanNode(None, merged_freq)
    merged_node.left = left_node
    merged_node.right = right_node

    # 3. 将新节点放回优先队列
    heapq.heappush(priority_queue, merged_node) # O(log N)

# 最后队列中剩下的唯一节点就是哈夫曼树的根
return priority_queue[0]

def generate_huffman_codes(root):
“””从哈夫曼树生成编码”””
codes = {}
def traverse(node, current_code):
if node is None:
return
# 如果是叶子节点 (代表一个字符)
if node.char is not None:
codes[node.char] = current_code if current_code else “0” # 处理只有一个字符的情况
return
# 递归遍历左右子树
traverse(node.left, current_code + “0”)
traverse(node.right, current_code + “1”)

traverse(root, "")
return codes

示例

char_freq = {‘a’: 45, ‘b’: 13, ‘c’: 12, ‘d’: 16, ‘e’: 9, ‘f’: 5}

频率总和 100

构建哈夫曼树

huffman_tree_root = build_huffman_tree(char_freq)

生成哈夫曼编码

huffman_codes = generate_huffman_codes(huffman_tree_root)

print(“哈夫曼编码:”)
total_length = 0
for char, freq in char_freq.items():
code = huffman_codes[char]
print(f”字符 ‘{char}’ (频率 {freq}): {code}”)
total_length += freq * len(code)

print(f”\n编码后的总长度: {total_length}”)

预期可能的编码 (具体 0/1 分配可能不同，但长度和结构应类似):

a: 0 (频率45, 长度1) -> 45*1 = 45

b: 101 (频率13, 长度3) -> 13*3 = 39

c: 100 (频率12, 长度3) -> 12*3 = 36

d: 111 (频率16, 长度3) -> 16*3 = 48

e: 1101 (频率9, 长度4) -> 9*4 = 36

f: 1100 (频率5, 长度4) -> 5*4 = 20

总长度 = 45+39+36+48+36+20 = 224 (这是一个例子，实际结果可能因合并时左右子树选择不同而编码不同，但总长度应是最小的224)

运行结果：

哈夫曼编码:

字符 ‘a’ (频率 45): 0

字符 ‘b’ (频率 13): 101

字符 ‘c’ (频率 12): 100

字符 ‘d’ (频率 16): 111

字符 ‘e’ (频率 9): 1101

字符 ‘f’ (频率 5): 1100

编码后的总长度: 224

“`

5. 复杂度分析：
– 设有 N 个字符。
– 构建最小堆：O(N)。
– 主循环执行 N-1 次合并。每次合并涉及两次 heappop (O(log N)) 和一次 heappush (O(log N))。
– 总时间复杂度：O(N) + (N-1) * O(log N) = O(N log N)。
– 生成编码需要遍历树，时间复杂度与树的节点数（最多 2N-1）和编码长度有关，通常也是 O(N * L_avg) 或 O(N log N) 级别，不超过建树复杂度。
– 空间复杂度：O(N) 用于存储优先队列和构建的树。

其他经典贪心算法

除了上述例子，还有许多著名的算法也运用了贪心思想：

• 最小生成树 (Minimum Spanning Tree, MST):

  • Prim 算法: 从一个顶点开始，每次贪心地选择连接已选顶点集合与未选顶点集合的、权值最小的边，并把对应的未选顶点加入集合，直到所有顶点都被包含。需要优先队列优化。
  • Kruskal 算法: 将所有边按权值从小到大排序，依次考虑每条边，如果这条边连接的两个顶点尚未连通（即加入该边不会形成环），则将其加入生成树，直到选够 N-1 条边。需要并查集 (Disjoint Set Union) 数据结构来检测环。
  • 这两种算法都依赖于贪心选择性质（基于割性质 Cut Property）和最优子结构。

• Dijkstra 算法 (单源最短路径):

  • 从源点开始，维护一个已找到最短路径的顶点集合 S。每次贪心地从不在 S 中的顶点里，选择一个当前估计距离源点最近的顶点 u，确认其最短路径并将 u 加入 S。然后更新 u 的所有邻居的估计距离。需要优先队列优化。
  • 注意: Dijkstra 算法的贪心性质要求边的权重不能为负。如果存在负权边，贪心选择（选当前距离最近的）可能不再满足贪心选择性质，需要使用 Bellman-Ford 等其他算法。

四、贪心算法的优势与局限性

优势 (Advantages):

1. 简单直观 (Simplicity): 贪心算法的思路通常比较直接，符合人类的直觉决策过程，易于理解和思考。
2. 高效 (Efficiency): 当贪心策略有效时，算法通常具有较低的时间复杂度，很多是 O(N log N) 或 O(N)，比动态规划或回溯搜索等方法快得多。
3. 易于实现 (Ease of Implementation): 相较于复杂的动态规划状态转移方程或回溯搜索的剪枝，贪心算法的实现通常更简洁。

局限性 (Disadvantages):

1. 不保证全局最优 (Not Always Optimal): 这是贪心算法最根本的局限。局部最优选择并不总能导向全局最优解。如前述的非规范币制找零和 0-1 背包问题。
2. 适用范围有限 (Limited Applicability): 只有满足贪心选择性质和最优子结构性质的问题才能使用贪心算法得到最优解。判断一个问题是否满足这两个性质，尤其是贪心选择性质，并不总是容易的，往往需要严格的数学证明。
3. 需要证明 (Proof Required): 不能凭直觉就断定一个贪心策略是正确的。必须经过严谨的证明，否则算法的正确性无法保证。证明过程有时可能相当复杂。
4. “短视” (Short-sighted): 贪心算法在做决策时只考虑当前状态的最优，不会“向前看”或考虑选择对未来的影响，也无法撤销之前的选择。这使得它无法处理那些需要权衡当前利益和长远利益的问题。
5. 难以调试 (Hard to Debug if Incorrect): 如果贪心算法给出了错误结果，往往是因为贪心策略本身有问题或不适用。找到反例或理解为什么策略失败可能需要深入分析。

五、贪心算法 vs 动态规划 (Greedy vs Dynamic Programming)

贪心算法和动态规划是解决优化问题的两种常用方法，它们都利用了最优子结构性质，但核心思想和适用场景有所不同。

特征	贪心算法 (Greedy Algorithm)	动态规划 (Dynamic Programming)
核心思想	每步做出当前看起来最好的选择 (局部最优)	分解问题，计算并存储所有子问题的最优解
决策依据	仅基于当前状态，做出唯一选择	考虑所有可能选择，选出导致最优子问题解的那个选择
关键性质	贪心选择性质 + 最优子结构性质	最优子结构性质 + 重叠子问题 (Overlapping Subproblems)
过程	一路向前，不回溯，不撤销选择	通常自底向上 (Tabulation) 或自顶向下带备忘录 (Memoization)
子问题处理	只关心由当前贪心选择导出的一个子问题	需要计算并存储所有相关子问题的解
保证最优解?	不一定 (需证明贪心选择性质)	是 (如果问题结构适合 DP)
效率	通常更高 (线性或 N log N)	通常较低 (多项式时间，如 N^2, N^3)
例子	活动选择, 分数背包, Huffman, Prim, Kruskal, Dijkstra	0-1 背包, 最长公共子序列 (LCS), 矩阵链乘

如何选择？

1. 尝试贪心： 对于一个优化问题，可以首先思考是否存在一个简单、直观的贪心策略。如果能找到，尝试证明其贪心选择性质。如果证明成功，那么贪心算法就是最佳选择（效率高）。
2. 考虑动态规划：
   • 如果找不到明显的贪心策略，或者贪心策略的反例很容易找到（即贪心选择性质不成立）。
   • 如果问题具有最优子结构性质，并且在做决策时需要权衡多种选择（即当前选择会影响后续子问题的构成或解），或者存在重叠子问题（即不同决策路径可能导致相同的子问题被反复计算）。
   • 那么动态规划通常是更合适的选择。

典型对比：分数背包 vs 0-1 背包
– 分数背包： 物品可分割。贪心策略（按价值密度）有效，因为可以取物品的一部分，总能优先利用最高密度的物品直到用完或背包满。满足贪心选择性质。
– 0-1 背包： 物品不可分割。按价值密度贪心可能导致选了一个密度高但重量大的物品后，剩余空间无法有效利用。局部最优（选密度最高的）不保证全局最优。需要动态规划来考虑“选这个物品”和“不选这个物品”两种情况及其对应的子问题。

六、总结与展望

贪心算法是一种强大而优雅的算法设计范式。它基于一个简单而诱人的思想：不断做出局部最优的选择，以期达到全局最优。当问题结构适宜时（满足贪心选择性质和最优子结构性质），贪心算法能以极高的效率（通常是多项式时间，甚至线性或近线性时间）找到精确的最优解。

我们通过找零钱、活动选择、分数背包、哈夫曼编码等经典实例，详细剖析了贪心算法的设计步骤：从问题建模、寻找贪心策略，到最关键的证明贪心选择的正确性，再到算法实现和复杂度分析。同时，我们也强调了贪心算法的局限性——它并非万能药，其“短视”的特点使其无法解决所有优化问题，特别是那些需要长远规划或权衡取舍的问题（如 0-1 背包）。

理解贪心算法的核心在于把握贪心选择性质和最优子结构性质这两个支柱，并认识到证明是应用贪心策略前不可或缺的一环。与动态规划相比，贪心算法更像是一位“乐观的快刀手”，决策迅速，勇往直前；而动态规划则更像是一位“深思熟虑的棋手”，稳扎稳打，考虑周全。

掌握贪心算法，不仅意味着能够应用 Prim、Kruskal、Dijkstra、Huffman 等经典算法，更重要的是培养一种分析问题的视角：能否通过一系列“聪明”的局部决策来解决问题？这种思维方式在计算机科学乃至日常生活的许多决策场景中都具有启发意义。

未来，随着问题规模的日益增大和对算法效率要求的不断提高，贪心思想及其变种（如近似贪心算法、随机贪心算法）将在更多领域发挥作用。深入理解其原理、优势与局限，将使我们能更好地驾驭这一工具，解决现实世界中的复杂优化挑战。希望本文能为你打下坚实的贪心算法基础，激发你进一步探索算法世界的兴趣。

---