贪心算法 (Greedy)
贪心算法(Greedy)
贪心算法每一步都选择当前最优解,期望通过局部最优达到全局最优。适用于满足贪心选择性质和最优子结构的问题。
原理与特点
- 每一步都做出当前最优选择,不回溯、不枚举所有可能
- 适合区间调度、资源分配、最小生成树等问题
- 有时不能保证全局最优,但实现简单、效率高
常见应用
- 区间调度
- 跳跃游戏
- 零钱兑换(部分情况)
- 分发糖果
- 买卖股票的最佳时机
- Huffman编码、最小生成树(Kruskal)
典型例题
1. 跳跃游戏
def canJump(nums):
farthest = 0
for i, x in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + x)
return True
2. 分发糖果
def candy(ratings):
n = len(ratings)
candies = [1]*n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1]+1)
return sum(candies)
优缺点
- 优点:实现简单,效率高
- 缺点:不一定得到全局最优解