编辑代码

# 定义Place结构体
class Place:
    def __init__(self, name: str, time: int, score: int):
        self.name = name
        self.time = time
        self.score = score


# 定义max函数
def max(a: int, b: int) -> int:
    return a if a > b else b


# 主函数
def main():
    # 构造测试数据  
    places = [Place("故宫", 1, 7), Place("颐和园", 2, 8), Place("长城", 3, 9), Place("天坛", 1, 6)]
    n = len(places)  # 使用len函数获取列表长度  
    days = 4  # 定义天数  
    dp = [[0] * (days + 1) for _ in range(n + 1)]  # 初始化动态规划数组  
    # 动态规划状态转移  
    for i in range(1, n + 1):
        for j in range(1, days + 1):
            if places[i - 1].time > j:  # 如果当前地点所需时间大于剩余天数，无法选择该地点，继承上一状态  
                dp[i][j] = dp[i - 1][j]
            else:  # 否则，计算选择当前地点的最大价值  
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - places[i - 1].time] + places[i - 1].score)

                # 输出最大价值
    print(f"最大价值为：{dp[n][days]}")
    # 输出最优解  
    i = n
    j = days
    visited = [False] * (days + 1)  # 使用visited列表记录哪些天已经访问过，初始化为False  
    while i > 0 and j > 0:  # 当还有地点和天数时，继续循环  
        if dp[i][j] != dp[i - 1][j]:  # 如果当前状态与不选择当前地点时的状态不同，说明选择了当前地点  
            print(places[i - 1].name, end=" ")  # 输出选择的地点名称  
            j -= places[i - 1].time  # 更新剩余天数，减去选择地点的所需时间  
            visited[j] = True  # 将已经访问的天数标记为True  
        i -= 1  # 选择下一个地点  
    print()  # 在输出地点名称后换行  


main()  # 运行主函数