贪心算法几个经典例子代码

贪心算法是一种简单而又实用的算法，在计算机科学中有着广泛的应用。贪心算法的基本思想是从问题的某一初始解出发，对其进行一系列的改进，以求得最优解。本文将从贪心算法的定义、特点及其几个经典例子进行介绍，并给出相应的代码实现。

一、贪心算法的定义

贪心算法，是指在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是最优的算法。贪心算法与动态规划算法类似，但它对每个子问题的解决方案都作出选择，不能回退。因此它分阶段地贪心，每个阶段可以利用上一个阶段可行的解，以求全局最优解。

二、贪心算法的特点

1.简单性：贪心算法是基于局部最优的策略来构建全局最优解的算法。由于它的策略是简单的，算法的实现也相对容易。

2.高效性：贪心算法采用逐步优化的方式，每次只考虑当前状态下的最优选择，因此它的时间复杂度通常较低。

3.局限性：贪心算法通常无法保证最终的解是全局最优解，因为它所做的选择每次只针对当前状态，未来的发展无法预测。

三、贪心算法几个经典例子

1. 零钱兑换问题

问题描述：假设有若干个不同面值的硬币，要找零k元，问最少需几个硬币？

解题思路：每次都选择面值最大的硬币，继续找零，直到找出k元。

核心代码：

```

def coinChange(coins: List[int], amount: int) -> int:

coins = sorted(coins, key=lambda x: -x)

ans = 0

for coin in coins:

ans += amount // coin

amount %= coin

return ans if amount == 0 else -1

```

2. 贪心背包问题

问题描述：有一背包可以放下一定重量的物品，现在有n个物品，每个物品有自己的价值和重量，在限定的重量范围内，如何选择物品放入背包中，使得背包中的总价值最大？

解题思路：每次选择单位重量价值最高的物品放入背包中。

核心代码：

```

def fractional_knapsack(w: List[float], v: List[float], c: float) -> float:

v_w = [(vi / wi, wi) for vi, wi in zip(v, w)]

v_w.sort(reverse=True)

ans = 0.0

for vi, wi in v_w:

if c > wi:

ans += vi * wi

c -= wi

else:

ans += vi * c

break

return ans

```

3. 区间调度问题

问题描述：有n个互不相交的区间，选择其中尽可能多的区间，使得这些区间之间没有相交的部分。

解题思路：每次选择结束时间最早的区间，排除已选区间后，继续对剩余区间进行选择。

核心代码：

```

def interval_schedule(intervals: List[Tuple[int, int]]) -> int:

intervals.sort(key=lambda x: x[1])

ans, end_time = 0, -float('inf')

for start, end in intervals:

if start >= end_time:

ans += 1

end_time = end

return ans

```