再举一个贪心算法的python例子
时间: 2023-03-08 11:55:51 浏览: 42
好的,下面是一个关于贪心算法的 Python 例子:
假设我们要选择一组物品以获得最大价值,其中每件物品都有一个体积和一个价值。我们可以使用贪心算法,每次选择价值密度最高的物品。
以下是代码实现:
```
def max_value(items, max_weight):
# 将物品按价值密度从大到小排序
items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
total_value = 0
total_weight = 0
for item in items:
if total_weight + item[0] <= max_weight:
total_weight += item[0]
total_value += item[1]
return total_value
# 测试
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
max_weight = 7
print(max_value(items, max_weight)) # Output: 10
```
在这个例子中,我们选择了价值密度最高的物品,直到不能再选择任何物品为止,以获得最大的价值。
相关问题
举个贪心算法的python例子
下面是一个贪心算法的简单 Python 代码例子,它解决了一个选择工作的问题:
```
# 假设有一些工作,每个工作有开始时间和结束时间
jobs = [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
# 按照结束时间排序
jobs.sort(key=lambda x: x[1])
# 初始化一个计数器,表示当前选择的工作数
count = 0
# 初始化一个时间点,表示当前可用的最早结束时间
cur_time = 0
# 遍历每个工作
for job in jobs:
# 如果当前工作的开始时间大于当前可用的最早结束时间
# 那么可以选择该工作
if job[0] >= cur_time:
count += 1
cur_time = job[1]
# 输出最多可以选择的工作数
print(count)
```
运行结果是:4,表示可以选择 4 个工作。
贪心算法几个经典例子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