编辑代码

def optimize_trip(days, places):
    n = len(places)
    dp = [[0] * (days + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, days + 1):
            time_needed = places[i - 1][0]
            score = places[i - 1][1]

            if j >= time_needed:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time_needed] + score)
            else:
                dp[i][j] = dp[i - 1][j]

    selected_places = []
    i, j = n, days
    while i > 0 and j > 0:
        if dp[i][j] != dp[i - 1][j]:
            selected_places.append(places[i - 1][2])
            j -= places[i - 1][0]
        i -= 1

    selected_places.reverse()
    return dp[n][days], selected_places

def main():
    days = 4
    places = [
        (1, 7, "故宫"),
        (2, 8, "颐和园"),
        (3, 9, "长城"),
        (1, 6, "天坛")
    ]

    total_score, selected_places = optimize_trip(days, places)

    print(f"在{days}天内，可以获得最大总评分为: {total_score}")
    print(f"选择的景点为: {', '.join(selected_places)}")

if __name__ == "__main__":
    main()