Python程序贪婪算法求活动安排问题
时间: 2024-02-16 08:57:25 浏览: 21
以下是Python程序贪婪算法求活动安排问题的示例代码:
```python
def activity_selection(start, finish):
n = len(finish)
i = 0
print("Selected activities:")
print(i, end=" ")
for j in range(n):
if start[j] >= finish[i]:
print(j, end=" ")
i = j
print()
# 示例
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
activity_selection(start, finish)
```
输出结果为:
```
Selected activities:
0 1 3 4
```
该算法的基本思路是:首先将所有活动按照结束时间从早到晚排序,然后从第一个活动开始,依次判断每个活动的开始时间是否晚于上一个活动的结束时间,如果是,则选择该活动,否则跳过该活动。最终选择的活动即为最大兼容活动集合。