用Python回朔法求活动安排问题的代码

以下是常见的活动安排问题的回溯算法的 Python 代码示例：

def activity_selection(start, end):
    n = len(end)
    selected = [False] * n

    def backtrack(last_end_time, k):
        nonlocal selected
        if k == n:
            return 0
        elif start[k] >= last_end_time:
            selected[k] = True
            return 1 + backtrack(end[k], k+1)
        else:
            selected[k] = False
            return backtrack(last_end_time, k+1)

    max_num_activities = backtrack(-float('inf'), 0)
    return max_num_activities, [i for i in range(n) if selected[i]]

# 示例用法
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
max_num_activities, selected = activity_selection(start, end)
print("最多可以参加 %d 个活动，编号分别为 %s" % (max_num_activities, selected))

注意：该算法并不保证一定得到最优解。如果您需要非常高效率的方案或求解规模非常大的问题，可能需要使用更为复杂的算法或优化方案。