编辑代码

def optimize_travel(scenic_spots, max_days):
    num_spots = len(scenic_spots)
    
    # 初始化动态规划数组
    dp = [[0] * (max_days + 1) for _ in range(num_spots + 1)]

    for i in range(1, num_spots + 1):
        for j in range(1, max_days + 1):
            # 不选择当前景点
            dp[i][j] = dp[i-1][j]
            # 选择当前景点，更新最大评分
            if j >= scenic_spots[i-1]['time']:
                dp[i][j] = max(dp[i][j], dp[i-1][j-scenic_spots[i-1]['time']] + scenic_spots[i-1]['score'])

    # 最大评分为最优解
    max_score = dp[num_spots][max_days]

    # 回溯找到所选景点
    selected_spots = []
    i, j = num_spots, max_days
    while i > 0 and j > 0:
        if dp[i][j] != dp[i-1][j]:
            selected_spots.append(scenic_spots[i-1]['name'])
            j -= scenic_spots[i-1]['time']
        i -= 1

    return max_score, selected_spots[::-1]

# 测试数据
scenic_spots = [
    {'name': '故宫', 'time': 1, 'score': 7},
    {'name': '颐和园', 'time': 2, 'score': 8},
    {'name': '长城', 'time': 3, 'score': 9},
    {'name': '天坛', 'time': 1, 'score': 6},
]

max_days = 4

# 打印结果
max_score, selected_spots = optimize_travel(scenic_spots, max_days)
print(f"最大评分：{max_score}")
print(f"选择的景点：{', '.join(selected_spots)}")