浅谈贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的局部选择，从而希望导致全局最优解的算法策略。其核心思想是“短视”地追求局部最优，不回溯、不修改已做出的选择。
1.适用条件
1.贪心选择性质：全局最优解可以通过局部最优选择达到。
2.最优子结构：问题的最优解包含其子问题的最优解。
2.算法步骤
1.建立数学模型：明确问题的优化目标。
2.分解子问题：将问题划分为多个子问题。
3.贪心选择：对每个子问题做出局部最优选择。
4.合并结果：将所有子问题的解合并为最终解。
3.经典问题示例
示例1：找零钱问题
问题描述：用最少数量的硬币凑出指定金额（假设硬币面值为 1, 5, 10, 20, 50, 100 元）。
贪心策略：每次选择最大面值硬币，直到凑满金额。
def coin_change(coins, amount):
coins.sort(reverse=True) # 降序排列面值
result = []
for coin in coins:
while amount >= coin:
result.append(coin)
amount -= coin
if amount == 0:
break
return result if amount == 0 else "无法找零"
# 示例
coins = [1, 5, 10, 20, 50, 100]
print(coin_change(coins, 63)) # 输出: [50, 10, 1, 1, 1]
示例2：活动选择问题
问题描述：从一组活动中选择最多互不冲突的活动（每个活动有开始和结束时间）。
贪心策略：优先选择最早结束的活动，为后续留出更多时间。
def select_activities(activities):
# 按结束时间升序排序
sorted_acts = sorted(activities, key=lambda x: x[1])
selected = [sorted_acts[0]]
for act in sorted_acts[1:]:
# 当前活动的开始时间 >= 上一个选中活动的结束时间
if act[0] >= selected[-1][1]:
selected.append(act)
return selected
# 示例
activities = [(1,4), (3,5), (0,6), (5,7), (8,9)]
# 输出: [(1,4), (5,7), (8,9)]
print(select_activities(activities))
4.贪心算法的局限性
-
不保证全局最优：例如若硬币面值为[25, 15, 1]，凑30分时贪心法会选25+5*1=6枚，而最优解是15+15=2枚。
-
依赖问题特性：必须满足贪心选择性质和最优子结构。
5.适用场景
-
最短路径问题（Dijkstra算法）
-
最小生成树（Prim、Kruskal算法）
-
霍夫曼编码
-
部分背包问题
通过以上示例可以看出，贪心算法实现简单且高效，但需谨慎验证问题的适用性。在实际应用中，务必先确认问题是否满足贪心算法的前提条件。