贪心算法经典例题（贪心算法经典例题讲解）

## 贪心算法经典例题### 简介贪心算法（Greedy Algorithm）是一种常用的算法思想，它的核心是在每一步选择中都选择当前状态下

局部最优解

，并期望通过一系列的局部最优选择最终得到

全局最优解

。 贪心算法并不适用于所有问题，它需要满足以下两个条件：1.

最优子结构性质:

问题的最优解包含其子问题的最优解。 2.

贪心选择性质:

每一步的局部最优选择可以导致全局最优解。### 经典例题#### 1. 找零钱问题##### 问题描述假设你是一个收银员，需要给顾客找零钱。你有一堆不同面值的硬币，如何使用最少的硬币数量来凑出目标金额？##### 算法思路贪心策略：每次都选择面值最大的硬币，直到凑齐目标金额。##### 代码示例 (Python)```python def make_change(coins, amount):"""找零钱问题Args:coins: 硬币面值列表amount: 目标金额Returns:使用的硬币数量，如果无法凑出则返回 -1"""coins.sort(reverse=True) # 从大到小排序num_coins = 0remaining = amountfor coin in coins:while remaining >= coin:remaining -= coinnum_coins += 1if remaining == 0:return num_coinselse:return -1# 测试 coins = [1, 5, 10, 25] amount = 41 print(make_change(coins, amount)) # 输出 4 ```##### 解释在这个例子中，我们总是优先选择面值最大的硬币。例如，对于目标金额 41，我们会优先选择 25，然后是 10，再是 5，最后是 1。#### 2. 活动选择问题##### 问题描述假设你有一个教室，以及一系列需要使用该教室的活动，每个活动都有一个开始时间和结束时间。如何在有限的时间内安排尽可能多的活动，且活动之间不会冲突？##### 算法思路贪心策略：每次都选择结束时间最早的活动，这样可以为后续活动留出更多的时间。##### 代码示例 (Python)```python def activity_selection(activities):"""活动选择问题Args:activities: 活动列表，每个活动用一个元组 (start_time, end_time) 表示Returns:最多可以安排的活动数量"""activities.sort(key=lambda x: x[1]) # 按结束时间排序selected = []last_end = 0for start, end in activities:if start >= last_end:selected.append((start, end))last_end = endreturn len(selected)# 测试 activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (6, 9), (8, 10), (9, 11)] print(activity_selection(activities)) # 输出 4 ```##### 解释我们首先按照活动的结束时间对活动列表进行排序。然后，我们选择结束时间最早的活动，并将该活动的结束时间作为下一个活动的开始时间的限制。重复这个过程，直到无法再选择更多的活动。#### 3. 区间调度问题##### 问题描述给定一些时间区间，每个区间表示一个任务的开始和结束时间。你需要找到最少需要多少个处理器才能完成所有任务，假设每个处理器在同一时间只能处理一个任务。##### 算法思路贪心策略：每次都选择结束时间最早的任务，并将其分配给空闲的处理器。如果当前没有空闲的处理器，则需要增加一个处理器。##### 代码示例 (Python)```python def interval_scheduling(intervals):"""区间调度问题Args:intervals: 时间区间列表，每个区间用一个元组 (start_time, end_time) 表示Returns:最少需要的处理器数量"""intervals.sort(key=lambda x: x[1]) # 按结束时间排序processors = []for start, end in intervals:allocated = Falsefor i in range(len(processors)):if processors[i] <= start:processors[i] = endallocated = Truebreakif not allocated:processors.append(end)return len(processors)# 测试 intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (6, 9), (8, 10), (9, 11)] print(interval_scheduling(intervals)) # 输出 3 ```##### 解释我们首先按照任务的结束时间对任务列表进行排序。然后，我们依次处理每个任务。对于每个任务，我们检查当前是否有空闲的处理器。如果有，则将该任务分配给该处理器；如果没有，则需要增加一个处理器。### 总结贪心算法是一种简单且有效的算法，但它并不总是能得到全局最优解。在使用贪心算法之前，我们需要仔细分析问题的性质，以确保它满足贪心算法的条件。

贪心算法经典例题

简介贪心算法（Greedy Algorithm）是一种常用的算法思想，它的核心是在每一步选择中都选择当前状态下**局部最优解**，并期望通过一系列的局部最优选择最终得到**全局最优解**。 贪心算法并不适用于所有问题，它需要满足以下两个条件：1. **最优子结构性质:** 问题的最优解包含其子问题的最优解。 2. **贪心选择性质:** 每一步的局部最优选择可以导致全局最优解。

经典例题

1. 找零钱问题

问题描述假设你是一个收银员，需要给顾客找零钱。你有一堆不同面值的硬币，如何使用最少的硬币数量来凑出目标金额？

算法思路贪心策略：每次都选择面值最大的硬币，直到凑齐目标金额。

代码示例 (Python)```python def make_change(coins, amount):"""找零钱问题Args:coins: 硬币面值列表amount: 目标金额Returns:使用的硬币数量，如果无法凑出则返回 -1"""coins.sort(reverse=True)

从大到小排序num_coins = 0remaining = amountfor coin in coins:while remaining >= coin:remaining -= coinnum_coins += 1if remaining == 0:return num_coinselse:return -1

测试 coins = [1, 5, 10, 25] amount = 41 print(make_change(coins, amount))

输出 4 ```

解释在这个例子中，我们总是优先选择面值最大的硬币。例如，对于目标金额 41，我们会优先选择 25，然后是 10，再是 5，最后是 1。

2. 活动选择问题

问题描述假设你有一个教室，以及一系列需要使用该教室的活动，每个活动都有一个开始时间和结束时间。如何在有限的时间内安排尽可能多的活动，且活动之间不会冲突？

算法思路贪心策略：每次都选择结束时间最早的活动，这样可以为后续活动留出更多的时间。

代码示例 (Python)```python def activity_selection(activities):"""活动选择问题Args:activities: 活动列表，每个活动用一个元组 (start_time, end_time) 表示Returns:最多可以安排的活动数量"""activities.sort(key=lambda x: x[1])

按结束时间排序selected = []last_end = 0for start, end in activities:if start >= last_end:selected.append((start, end))last_end = endreturn len(selected)

测试 activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (6, 9), (8, 10), (9, 11)] print(activity_selection(activities))

输出 4 ```

解释我们首先按照活动的结束时间对活动列表进行排序。然后，我们选择结束时间最早的活动，并将该活动的结束时间作为下一个活动的开始时间的限制。重复这个过程，直到无法再选择更多的活动。

3. 区间调度问题

问题描述给定一些时间区间，每个区间表示一个任务的开始和结束时间。你需要找到最少需要多少个处理器才能完成所有任务，假设每个处理器在同一时间只能处理一个任务。

算法思路贪心策略：每次都选择结束时间最早的任务，并将其分配给空闲的处理器。如果当前没有空闲的处理器，则需要增加一个处理器。

代码示例 (Python)```python def interval_scheduling(intervals):"""区间调度问题Args:intervals: 时间区间列表，每个区间用一个元组 (start_time, end_time) 表示Returns:最少需要的处理器数量"""intervals.sort(key=lambda x: x[1])

按结束时间排序processors = []for start, end in intervals:allocated = Falsefor i in range(len(processors)):if processors[i] <= start:processors[i] = endallocated = Truebreakif not allocated:processors.append(end)return len(processors)

测试 intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (6, 9), (8, 10), (9, 11)] print(interval_scheduling(intervals))

输出 3 ```

解释我们首先按照任务的结束时间对任务列表进行排序。然后，我们依次处理每个任务。对于每个任务，我们检查当前是否有空闲的处理器。如果有，则将该任务分配给该处理器；如果没有，则需要增加一个处理器。

总结贪心算法是一种简单且有效的算法，但它并不总是能得到全局最优解。在使用贪心算法之前，我们需要仔细分析问题的性质，以确保它满足贪心算法的条件。