贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法策略。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
核心思想
贪心算法的核心思想是：每一步都做出局部最优选择，期望这些局部最优选择能够导致全局最优解。
算法原理
基本特征
贪心选择性质：每一步的局部最优选择能导致全局最优解
最优子结构：问题的最优解包含其子问题的最优解
适用场景
问题具有贪心选择性质
问题具有最优子结构
不需要考虑未来的后果，当前最优就是全局最优
算法步骤拆解
问题分析：确定问题是否适合贪心算法
选择策略：确定每一步的贪心选择标准
可行性检查：检查选择是否满足问题约束
解决方案构建：将贪心选择逐步组合成完整解
最优性验证：验证最终解是否最优
经典问题示例
1. 找零钱问题
pythondef coin_change_greedy(amount, coins):
"""
找零钱问题的贪心算法实现
:param amount: 需要找零的金额
:param coins: 可用硬币面值列表（降序排列）
:return: 每种硬币的数量字典
"""
coins.sort(reverse=True) # 按面值从大到小排序
result = {}
for coin in coins:
if amount >= coin:
count = amount // coin
result[coin] = count
amount -= coin * count
if amount > 0:
print(f"无法完全找零，剩余金额: {amount}")
return result
# 示例
coins = [100, 50, 20, 10, 5, 1] # 可用硬币面值
amount = 176
change = coin_change_greedy(amount, coins)
print(f"找零 {amount} 元的结果: {change}")
执行过程拆解：
剩余176元，选择100元硬币：1个，剩余76元
剩余76元，选择50元硬币：1个，剩余26元
剩余26元，选择20元硬币：1个，剩余6元
剩余6元，选择5元硬币：1个，剩余1元
剩余1元，选择1元硬币：1个，完成
2. 活动选择问题
pythondef activity_selection(activities):
"""
活动选择问题的贪心算法实现
:param activities: 活动列表，每个活动为(start, end)元组
:return: 选择的活动列表
"""
# 按结束时间排序
activities.sort(key=lambda x: x[1])
selected = []
last_end = 0
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)]
selected = activity_selection(activities)
print("选择的活动:")
for i, (start, end) in enumerate(selected, 1):
print(f"活动{i}: {start} - {end}")
执行过程拆解：
按结束时间排序后：[(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
选择(1,4)，最后结束时间=4
选择(5,7)，最后结束时间=7
选择(8,11)，最后结束时间=11
选择(12,16)，最后结束时间=16
3. 背包问题（分数背包）
pythondef fractional_knapsack(capacity, items):
"""
分数背包问题的贪心算法实现
:param capacity: 背包容量
:param items: 物品列表，每个物品为(weight, value)元组
:return: 最大价值和物品选择方案
"""
# 计算单位价值并排序
items_with_ratio = [(weight, value, value/weight) for weight, value in items]
items_with_ratio.sort(key=lambda x: x[2], reverse=True)
total_value = 0
selected = []
for weight, value, ratio in items_with_ratio:
if capacity >= weight:
# 可以完整放入
total_value += value
capacity -= weight
selected.append((weight, value, 1.0)) # 完整放入
else:
# 只能放入一部分
fraction = capacity / weight
total_value += value * fraction
selected.append((weight, value, fraction))
break
return total_value, selected
# 示例
capacity = 50
items = [(10, 60), (20, 100), (30, 120)] # (重量, 价值)
max_value, selection = fractional_knapsack(capacity, items)
print(f"最大价值: {max_value}")
print("选择的物品:")
for weight, value, fraction in selection:
print(f" 重量{weight}, 价值{value}, 放入比例: {fraction:.2f}")
常见题型
区间调度
最大不相交子集。
无重叠区间open in new window
跳跃游戏
字符串
剑指 Offer II 019. 最多删除一个字符得到回文
贪心算法的优缺点
优点：
实现简单，易于理解
运行效率高，时间复杂度通常较低
对于适合的问题，能得到最优解
缺点：
不适用于所有问题
可能得到局部最优而非全局最优
需要证明贪心策略的正确性
只要可以通过局部最优达到全局最优解，就可以使用贪心算法，然而只有一部分问题拥有这个性质，故只能在特定的问题下使用贪心算法。
贪心算法 vs 动态规划
特性贪心算法动态规划决策依据当前最优所有可能时间复杂度通常较低通常较高空间复杂度通常较低通常较高适用范围特定类型问题更广泛解的质量可能不是最优保证最优
贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别。
实践建议
验证贪心选择性：确保局部最优能导致全局最优
分析问题结构：检查是否具有最优子结构
设计贪心策略：确定每一步的最优选择标准
实现并测试：编写代码并进行充分测试
证明正确性：数学证明或逻辑推理验证算法正确性
贪心算法是一种强大而高效的算法策略，在适合的问题上能够提供简洁优美的解决方案。理解其原理和适用场景对于算法设计和问题解决具有重要意义。