贪心算法几个经典例子Python

以下是几个经典的贪心算法例子的 Python 代码：

1. 零钱兑换问题

'''
题目描述：给定一个整数金额和一些硬币，求出能够组成该金额的最少硬币数。

例如，当金额为 11 时，硬币面值为 [1, 2, 5]，应返回 3（5元硬币1枚，2元硬币2枚）。

思路：贪心策略是每次尽可能使用面值最大的硬币，直到金额为 0。

'''

def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount == 0:
break
if coin <= amount:
count += amount // coin
amount = amount % coin
return count if amount == 0 else -1

2. 活动选择问题

'''
题目描述：假设有 n 个活动，每个活动都有一个开始时间和结束时间。选择一些活动，使得它们不冲突，且能够参加的活动数最多。

例如，有以下 6 个活动：
[ (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9) ]

其中，选择 (0, 6), (6, 7), (7, 8), (8, 9) 四个活动，即可参加的活动数最多。

思路：贪心策略是每次选择结束时间最早的活动，并且该活动与前面选择的活动不冲突。

'''

def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = []
end_time = -1
for activity in activities:
if activity[0] >= end_time:
selected.append(activity)
end_time = activity[1]
return selected

3. 分糖果问题

'''
题目描述：给定两个列表，分别表示 n 个孩子的糖果数和 m 个糖果的大小。要求将糖果分给孩子，使得每个孩子最多只能分到一个糖果，并且尽可能多的孩子能够分到糖果。

例如，有 3 个孩子，糖果大小为 [1, 2, 3]，糖果数为 [1, 1]，则最多只能分配 2 个孩子，因为第三个孩子没有糖果可分。

思路：贪心策略是每次尽可能给糖果大小最小且能够满足该孩子的糖果。

'''

def candy(children, candies):
children.sort()
candies.sort()
i = j = 0
count = 0
while i < len(children) and j < len(candies):
if candies[j] >= children[i]:
count += 1
i += 1
j += 1
return count