编辑代码

def optimize_travel(days_available, attractions):
    # 创建一个二维数组来保存每个子问题的解
    dp = [[0] * (days_available + 1) for _ in range(len(attractions) + 1)]
    
    # 填充动态规划表格
    for i in range(1, len(attractions) + 1):
        for j in range(1, days_available + 1):
            # 当前景点的时间大于剩余天数，无法选择该景点
            if attractions[i-1][1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                # 选择当前景点和不选择当前景点中的较大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-attractions[i-1][1]] + attractions[i-1][2])
    
    # 回溯找出最优解的景点组合
    selected_attractions = []
    i, j = len(attractions), days_available
    while i > 0 and j > 0:
        if dp[i][j] != dp[i-1][j]:
            selected_attractions.append(attractions[i-1][0])
            j -= attractions[i-1][1]
        i -= 1
    
    # 返回最优解的景点组合和总评分
    return selected_attractions, dp[len(attractions)][days_available]

# 景点列表
attractions = [("故宫", 1, 7), ("颐和园", 2, 8), ("长城", 3, 9), ("天坛", 1, 6)]
# 可用天数
days_available = 4

selected_attractions, total_score = optimize_travel(days_available, attractions)

print("去以下景点能够获得最大价值:")
for attraction in selected_attractions:
    print(attraction)
print("总评分:", total_score)