回溯法求活动安排问题python代码

以下是回溯法求活动安排问题的Python代码：

def activity_selection(start, end):
    n = len(end)
    selected = [False]*n
    selected[0] = True
    last_end_time = end[0]
    for i in range(1, n):
        if start[i] >= last_end_time:
            selected[i] = True
            last_end_time = end[i]
    return selected

start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
selected = activity_selection(start, end)
for i in range(len(selected)):
    if selected[i]:
        print("Activity {} is selected".format(i+1))

这段代码使用回溯法求解活动安排问题，即在一组活动中选择不冲突的活动，使得能够参加的活动数最大。函数 `activity_selection` 接受开始时间和结束时间两个数组作为参数，返回一个布尔数组 `selected`，其中 `selected[i]` 表示第 i 个活动是否被选择。在主函数中，我们打印出被选择的活动的编号。