使用Python解决以下问题的代码:对于给定的一系列活动ai,其对应的开始时间为si,结束时间为fi,每个活动还有一个对应的权值vi,请在这些活动中找出若干个相容的且总的权值最大的活动。请用贪心算法解决,
时间: 2024-10-17 15:13:45 浏览: 18
要解决这个问题,我们可以使用贪心算法。首先,我们需要对活动按照结束时间进行排序。然后,我们可以遍历排序后的活动列表,选择当前活动,并确保它与已选择的活动不冲突(即开始时间晚于或等于上一个活动的结束时间)。同时,我们需要记录每个被选中活动的权值,并在最后计算总权值。
以下是解决此问题的Python代码:
```python
def max_weighted_activities(activities):
# 按结束时间对活动进行排序
activities.sort(key=lambda x: x[2])
# 初始化结果列表和最大权值
result = []
max_weight = 0
# 遍历排序后的活动列表
for activity in activities:
ai, si, fi, vi = activity
# 如果结果列表为空或者当前活动的开始时间大于等于上一个活动的结束时间
if not result or si >= result[-1][2]:
# 将当前活动添加到结果列表中
result.append(activity)
# 更新最大权值
max_weight += vi
return result, max_weight
# 示例活动列表,每个元素为 (ai, si, fi, vi)
activities = [
('A', 1, 3, 5),
('B', 2, 4, 6),
('C', 3, 5, 7),
('D', 4, 6, 8),
('E', 5, 7, 9)
]
result, max_weight = max_weighted_activities(activities)
print("选取的活动:", result)
print("最大权值:", max_weight)
```
这段代码首先定义了一个名为`max_weighted_activities`的函数,该函数接受一个活动列表作为输入。活动列表中的每个元素都是一个包含四个元素的元组,分别表示活动标识符、开始时间、结束时间和权值。函数返回一个包含所选活动和最大权值的元组。
阅读全文