请python编程实现以下问题的贪心算法,活动选择问题(加权)
时间: 2024-10-13 08:11:08 浏览: 32
在Python中,我们可以使用贪心算法来解决活动选择问题(也称为任务调度或项目选择)。这个问题通常涉及到给定一系列活动,每个活动有一个开始时间和结束时间,以及一个价值。我们的目标是在一天内选择总价值最大的活动集合,使得所有选中的活动不会冲突。
下面是一个简单的贪心算法实现,我们假设活动按照结束时间降序排序:
```python
def activity_selection(activities):
# 按照结束时间降序排序
activities.sort(key=lambda x: -x[1])
result = []
current_end = float('-inf') # 初始结束时间为负无穷大
for activity in activities:
if activity[0] >= current_end: # 如果这个活动开始时间晚于当前活动的结束时间,可以安排
result.append(activity)
current_end = activity[1] # 更新当前活动的最大结束时间
return result
# 示例:
activities = [(1, 7, 5), (2, 4, 1), (3, 6, 3), (8, 10, 2)]
print("选择的活动:", activity_selection(activities))
```
在这个例子中,贪心策略就是每次都选择结束时间最早的一个活动,因为这将最大化剩余时间内的收益。
阅读全文