如何使用Python编写代码来解决活动选择问题，目标是找到具有最高总价值的一组活动？

在Python中，我们可以使用回溯法（backtracking）来解决活动选择问题，如"人狼羊菜过河"游戏中的最优化版本。这个问题通常涉及给定一系列活动，每个活动有一个开始时间、结束时间和价值，目标是选择能完成的活动组合以最大化总价值，同时避免冲突（即两个活动不能同时进行）。

下面是一个简单的示例，使用回溯法来解决活动选择问题[^1]：

# 假设我们有以下活动数据（start, end, value）
activities = [
    (1, 3, 10),
    (2, 4, 20),
    (3, 6, 30),
    (4, 7, 40)
]

def activity_selection(activities, current_time=0):
    best_value = 0
    selected_activities = []

    def can_select(activity):
        return activity[0] >= current_time

    def backtrack(time, remaining_activities):
        nonlocal best_value, selected_activities
        if not remaining_activities:
            # 如果当前时间大于所有活动的结束时间，则更新最佳值
            if time > max(activity[1] for activity in activities):
                if sum(activity[2] for activity in selected_activities) > best_value:
                    best_value = sum(activity[2] for activity in selected_activities)
                    selected_activities = [activity for activity in activities if activity in selected_activities]
        else:
            # 对于剩余活动，尝试选入并递归处理
            for i, activity in enumerate(remaining_activities):
                if can_select(activity):
                    selected_activities.append(activity)
                    backtrack(time + activity[1], remaining_activities[:i] + remaining_activities[i+1:])
                    selected_activities.pop()

    backtrack(current_time, activities)
    return best_value, selected_activities

best_value, selected_activities = activity_selection(activities)
print(f"最高总价值: {best_value}, 活动组合: {selected_activities}")

在这个代码中，`activity_selection` 函数通过回溯遍历所有可能的活动组合，每次都尝试选择一个符合条件（不与已选活动冲突）的新活动。如果达到无法再添加新活动的状态（当前时间超过所有活动的结束时间），则检查当前的选择是否比之前最好。