千帆杯第一期赛题：游乐场排队规划助手(香港迪士尼python解法)

import pandas as pd
# 文件确认和数据读取
try:
    data = pd.read_excel('disneyland_projects.xlsx')
    print("文件读取成功！")
except Exception as e:
    print(f"文件读取失败：{e}")
    exit()
# 时间转换
play_time = 5 * 60  # 5小时转换为分钟
# 动态规划算法应用
def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    selected_items = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] > dp[i - 1][w] and weights[i - 1] <= w:
            selected_items.append(i - 1)
            w -= weights[i - 1]
    return dp[n][capacity], [data.iloc[index]['娱乐名称'] for index in selected_items[::-1]]
# 提取刺激指数和游玩时间
stimulation_indices = data['刺激指数(分)'].tolist()
play_durations = data['排队+游玩时间(分钟)'].tolist()
# 计算最大刺激指数和对应的项目组合
max_stimulation, projects_combination = knapsack(stimulation_indices, play_durations, play_time)
# 结果输出
print(f"在限定时间内，最大的刺激指数总和为：{max_stimulation}")
print(f"对应的娱乐项目组合为：{', '.join(projects_combination)}")

import pandas as pd
# 读取数据
df = pd.read_excel('disneyland_projects.xlsx')
# 提取必要的信息
projects = df['娱乐名称'].tolist()
times = df['排队+游玩时间(分钟)'].tolist()
visual_scores = df['视觉体验指数(分)'].tolist()
# 初始化动态规划表格
n = len(projects)
T = 120  # 总时间
dp = [[0] * (T + 1) for _ in range(n + 1)]
# 填充动态规划表格
for i in range(1, n + 1):
    for t in range(1, T + 1):
        if times[i - 1] <= t:
            dp[i][t] = max(dp[i - 1][t], dp[i - 1][t - times[i - 1]] + visual_scores[i - 1])
        else:
            dp[i][t] = dp[i - 1][t]
# 回溯找到选择的项目
selected_projects = []
t = T
for i in range(n, 0, -1):
    if times[i - 1] <= t and dp[i][t] > dp[i - 1][t]:
        selected_projects.append(projects[i - 1])
        t -= times[i - 1]
# 输出结果
print(f"在{T}分钟内，您可以获得的最大视觉体验指数是：{dp[n][T]}分。")
print(f"对应的娱乐项目组合是：{selected_projects[::-1]}。")