贪心算法
贪心算法（Greedy Algorithm）每步选当前最优——不保证全局最优，但对某些问题（如 Dijkstra、哈夫曼编码）贪心就是最优解
🎪 如何参加尽可能多的社团活动？
开学了，学校的社团都在招新。每个社团有一个活动时间——比如”动漫社 14:00-15:30”、“篮球社 15:00-16:00”、“音乐社 16:00-17:30”……
你精力有限，不能同时参加两个时间重叠的活动。问：最多能参加多少个社团活动？
这个问题有一个非常简单的解法：
每次选择”结束时间最早”的那个活动，然后排除掉所有和它冲突的活动。
这就是贪心算法（Greedy Algorithm）：每步都做出当前最好的选择，不回头、不改写。
🛍️ **类比：逛超市，买最贵的商品”
你妈给了你 100 块钱去超市买东西，说”买最值钱的”。
贪心策略：每次最贵的商品拿一个——不管后面还有没有更合适的组合，先拿当前最贵的。
全局最优呢？ 不一定！如果最贵的商品 99 元，剩下 1 元买不了别的。不如买一个 50 元的加一个 48 元的——总价值 98 > 99。所以贪心不一定是最优的——但在某些问题中，贪心就是正确的。
关键问题：什么时候贪心是正确的？
🤔 贪心的核心思想
贪心算法非常简单直接——每步选当前看起来最好的：
def greedy_algorithm(problem):
solution = []
while problem 还有选择:
best = 当前看起来最好的选择 # 贪心选择
solution.append(best)
problem = 去掉和 best 冲突的部分
return solution
两种核心性质：
- 贪心选择性质（Greedy Choice Property）：局部最优选择能导出全局最优解——不需要考虑”选了当前好的会不会导致后面选不到更好的”
- 最优子结构（Optimal Substructure）：和 DP 一样——子问题的最优解是全局最优解的一部分
贪心和 DP 的关系：
DP：考虑所有可能的选择，选择最优的那个（全面但可能慢）
贪心：只考虑当前最好的选择（快但不一定正确）
✅ 什么时候贪心是正确的？
活动选择问题（Activity Selection）
def max_activities(activities):
"""
activities: [(start1, end1), (start2, end2), ...]
返回最多能参加的活动数
"""
# 按结束时间排序
activities.sort(key=lambda x: x[1])
count = 1
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end: # 不冲突
count += 1
last_end = end
return count
activities = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(max_activities(activities)) # 4
为什么选”最早结束”是对的？ 因为结束时间越早，留给后续活动的时间越多。数学证明：如果存在一个最优解，它一定包含最早结束的活动。
找零问题（Coin Change）
def min_coins(coins, amount):
"""
用最少的硬币凑出 amount（假设硬币面额是标准美分）
coins = [25, 10, 5, 1] → 贪心就是最优的
"""
coins.sort(reverse=True)
result = []
for coin in coins:
while amount >= coin:
result.append(coin)
amount -= coin
return result
print(min_coins([25, 10, 5, 1], 63)) # [25, 25, 10, 1, 1, 1] → 6 枚
但贪心不总是对找零问题有效！
# 如果硬币面额是 [1, 3, 4]，要凑 6
# 贪心：4 + 1 + 1 = 3 枚
# 最优：3 + 3 = 2 枚 ← 贪心失败了！
结论：标准的美分硬币体系（25, 10, 5, 1）贪心是正确的——因为大面额是小面额的倍数。但任意面额下，需要 DP 才能保证最优。
🌟 贪心算法的经典应用
| 问题 | 贪心策略 | 是否最优？ |
|---|---|---|
| 活动选择 | 选最早结束的 | ✅ 是 |
| 哈夫曼编码 | 合并频率最小的两个字符 | ✅ 是 |
| Dijkstra 最短路径 | 选距离最近的点 | ✅ 是（非负权） |
| Prim 最小生成树 | 选到 MST 最近的点 | ✅ 是 |
| Kruskal 最小生成树 | 选最短的边 | ✅ 是 |
| 找零（标准硬币） | 从大面额开始用 | ✅ 是 |
| 找零（任意面额） | 同上 | ❌ 不一定，需要 DP |
案例：哈夫曼编码（Huffman Coding）
哈夫曼编码是数据压缩的基础算法——给出现频率高的字符分配短的编码，出现频率低的分配长的编码：
import heapq
from collections import Counter
def huffman_encoding(text):
# 统计频率
freq = Counter(text)
# 构建最小堆（按频率）
heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(heap)
# 贪心：每次合并两个频率最小的节点
while len(heap) > 1:
lo = heapq.heappop(heap) # 频率最小的
hi = heapq.heappop(heap) # 第二小的
for pair in lo[1:]:
pair[1] = '0' + pair[1] # 左边加 0
for pair in hi[1:]:
pair[1] = '1' + pair[1] # 右边加 1
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heap[0][1:], key=lambda p: p[0])
# 例子
text = "AABBBCCCCDDDDD"
codes = huffman_encoding(text)
print(codes) # [('A', '11'), ('B', '10'), ('C', '01'), ('D', '00')]
哈夫曼的贪心策略：每次合并频率最小的两个字符——这是正确的，因为数学上可以证明这种贪心策略构建的树具有最小的加权路径长度。
⚠️ 贪心的陷阱——什么时候不能用？
# 背包问题的变体：
# 0/1 背包（每个物品要么选要么不选）→ 贪心不行！
# 分数背包（物品可以切分）→ 贪心可行！
# 场景：背包容量 50
# 物品：A(重量10, 价值60, 单价6)
# B(重量20, 价值100, 单价5)
# C(重量30, 价值120, 单价4)
# 贪心（按单价从高到低）：先装 A、再装 B → 总价值 60+100=160
# 最优解：B + C → 总价值 100+120=220 ← 贪心失败！
# 但如果是分数背包（可以切一半）：
# 贪心：A、B、C(20) → 60+100+80=240 ✅ 最优
为什么分数背包贪心有效，0/1 背包不行？ 因为分数背包中，“选当前单价最高的”不会影响后续选择——你总是可以接着选。但 0/1 背包中，选了当前单价最高的可能用掉了容量，导致后面选不到更好的组合。
⚔️ 贪心 vs DP——什么时候用哪个？
| 问题特征 | 推荐算法 |
|---|---|
| 每步选当前最好的 → 结果就是全局最优 | 贪心 |
| 需要”看一下未来”才能做决定 | DP |
| 子问题完全独立 | 分治 |
| 子问题重叠且需要比较不同选择 | DP |
| 目标可以”切分”（分数背包） | 贪心 |
| 目标是离散的”选或不选” | DP |
快速判断：
- 能证明贪心选择性质成立 → 用贪心（简单、高效）
- 不能证明、但有最优子结构和重叠子问题 → 用 DP
- 不确定 → 先从 DP 入手，如果发现每步的最优选择”显然正确”再优化为贪心
📝 小结
| 概念 | 一句话 |
|---|---|
| 贪心算法 | 每步选当前最优，不回头不改写 |
| 贪心选择性质 | 局部最优能导出全局最优——需要证明 |
| 适用场景 | 活动选择、哈夫曼编码、Dijkstra、MST |
| 局限 | 不是所有问题贪心都是最优的 |
| 贪心 vs DP | 贪心简单但适用范围小，DP 全面但复杂 |
🎯 思考题：在”找零”问题中，当硬币面额是 [1, 5, 10, 25]（美分标准）时，贪心是最优的。但如果面额是 [1, 5, 10, 20, 25]，贪心还会是最优的吗？为什么？（提示：考虑凑 40 美分）
为什么先学这个？ 贪心是”只考虑眼前”的策略。另一种算法设计思想是”先尝试，不行再回头”——回溯与剪枝。