活动选择问题python
时间: 2023-07-28 08:14:12 浏览: 54
活动选择问题是经典的动态规划问题,可以使用贪心算法或动态规划算法解决。下面给出一个使用动态规划算法解决活动选择问题的 Python 代码示例:
```python
def max_activities(activities, start, finish):
# 按结束时间排序
sorted_activities = sorted(zip(finish, activities))
n = len(activities)
dp = [0] * n
dp[0] = 1
for i in range(1, n):
dp[i] = max(dp[j] for j in range(i) if sorted_activities[j][0] <= sorted_activities[i][1]) + 1
return dp[n-1]
# 示例
activities = ['A', 'B', 'C', 'D', 'E', 'F']
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(max_activities(activities, start, finish)) # 输出 4,即选择 A、B、D、F 这 4 个活动
```
在上面的代码中,`max_activities` 函数接受三个参数,分别是 `activities`、`start` 和 `finish`。其中,`activities` 是一个列表,表示各个活动的名称;`start` 是一个列表,表示各个活动的开始时间;`finish` 是一个列表,表示各个活动的结束时间。
在函数中,首先将所有活动按照结束时间排序,然后使用一个 `dp` 列表存储每个活动作为最后一个活动时,能够选择的最多活动数量。初始时,第一个活动的 `dp` 值为 1,然后从第二个活动开始遍历,对于每个活动,找到所有结束时间早于它的活动,计算它们的 `dp` 值,并取最大值加 1 就是当前活动的 `dp` 值。最终,`dp` 列表中的最大值即为能够选择的最多活动数量。
需要注意的是,上面的代码中并没有输出具体选哪些活动,如果需要输出具体解,可以再使用一些技巧进行处理。