多容量背包装数最大化算法求解Ragnar接力赛赛段覆盖优化问题

问题背景 #

该问题对应Ragnar接力赛的实际场景，目标是让一组可跑里程不同的跑者，在不跳过赛段的前提下覆盖尽可能多的接力赛段。

问题抽象 #

可抽象为带顺序约束的多容量背包装数最大化问题：

• 接力赛段视为有序数值列表，单位为英里
• 跑者的最大可跑里程视为不同容量的背包
• 核心要求：将尽可能多的赛段数值按顺序装入背包，赛段可多次复用，可任选赛段作为起始点，给定起始赛段后计算最多可覆盖的赛段数量。

已知参数 #

36个赛段的里程列表：

legs = [3.3, 4.2, 5.2, 3, 2.7, 4, 
        5.3, 4.5, 3, 5.8, 3.3, 4.9, 
        3.1, 3.2, 4, 3.5, 4.9, 2.3, 
        3.2, 4.6, 4.5, 4, 5.3, 5.9, 
        2.8, 1.9, 2.1, 3, 2.5, 5.6, 
        1.3, 4.6, 1.5, 1.2, 4.1, 8.1]

跑者可跑里程列表：

runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]

示例输出参考 #

Total run mileage = 32.0
Total legs covered = 7 (L1, L2, L3, L4, L5, L6, L7) Total mileage used = 27.7
Total mileage wasted = 4.3
{'Total': 3.2, 'Reminder': 0.2, 'Index': 0, 'L4': 3}
{'Total': 12.3, 'Reminder': 0.8, 'Index': 1, 'L1': 3.3, 'L2': 4.2, 'L6': 4}
{'Total': 5.2, 'Reminder': 0.0, 'Index': 2, 'L3': 5.2}
{'Total': 2.9, 'Reminder': 0.2, 'Index': 3, 'L5': 2.7}
{'Total': 2.9, 'Reminder': 2.9, 'Index': 4}
{'Total': 5.5, 'Reminder': 0.2, 'Index': 5, 'L7': 5.3}

该问题规模极小（跑者仅6人，赛段仅36个），优先选择动态规划算法获取全局精确最优解，算法逻辑如下：

1. 状态定义：dp[k][p] 表示使用前k个跑者，当前已覆盖到第p个赛段时，累计覆盖的最大赛段数量；额外维护路径表path[k][p]记录当前状态下第k个跑者分配的赛段区间，用于后续结果回溯。
2. 前缀和预处理：提前计算赛段里程的前缀和数组，可在O(1)时间内算出任意连续赛段的总里程，加速状态转移计算。
3. 状态转移：对每个跑者k，每个当前已覆盖到的赛段位置p，枚举该跑者从p开始最多能连续跑的赛段数t（满足连续t个赛段总里程 ≤ 跑者k的最大可跑里程），更新状态dp[k+1][p+t] = max(dp[k+1][p+t], dp[k][p] + t)，同时记录路径。如果支持赛段复用，只需把赛段序列视为环形可循环枚举即可。
4. 边界条件：初始状态dp[0][start] = 0，start为给定的起始赛段索引，其余状态初始化为-1表示不可达。
5. 结果回溯：遍历所有dp[len(runs)][p]找到最大值，即为最多可覆盖的赛段数，反向查路径表即可得到每个跑者的赛段分配结果。
   如果后续规模扩大（比如跑者超过20人，赛段超过100个），可以加入剪枝优化，跳过明显不可能得到更优解的状态分支。

def max_covered_legs(legs, runs, start_idx=0):
    n_legs = len(legs)
    n_runners = len(runs)
    # 前缀和预处理
    prefix = [0.0]*(n_legs+1)
    for i in range(n_legs):
        prefix[i+1] = prefix[i] + legs[i]
    # 初始化DP和路径表
    dp = [[-1]*(n_legs+1) for _ in range(n_runners+1)]
    path = [[None]*(n_legs+1) for _ in range(n_runners+1)]
    dp[0][start_idx] = 0
    # 填充DP
    for k in range(n_runners):
        cap = runs[k]
        for p in range(n_legs+1):
            if dp[k][p] == -1:
                continue
            # 不分配任何赛段给当前跑者
            if dp[k+1][p] < dp[k][p]:
                dp[k+1][p] = dp[k][p]
                path[k+1][p] = (p, 0)
            # 枚举最多能跑的连续赛段
            max_t = 0
            for t in range(1, n_legs - p + 1):
                if prefix[p+t] - prefix[p] <= cap + 1e-8: # 浮点误差处理
                    max_t = t
                else:
                    break
            for t in range(1, max_t+1):
                if dp[k+1][p+t] < dp[k][p] + t:
                    dp[k+1][p+t] = dp[k][p] + t
                    path[k+1][p+t] = (p, t)
    # 找最大覆盖数
    max_cnt = -1
    best_p = start_idx
    for p in range(n_legs+1):
        if dp[n_runners][p] > max_cnt:
            max_cnt = dp[n_runners][p]
            best_p = p
    # 回溯路径
    res = [None]*n_runners
    cur_p = best_p
    for k in range(n_runners-1, -1, -1):
        prev_p, t = path[k+1][cur_p]
        res[k] = (prev_p, t)
        cur_p = prev_p
    # 生成输出
    total_run = sum(runs)
    total_used = prefix[best_p] - prefix[start_idx]
    total_waste = total_run - total_used
    covered_legs = [f"L{i+1}" for i in range(start_idx, best_p)]
    print(f"Total run mileage = {total_run:.1f}")
    print(f"Total legs covered = {max_cnt} ({', '.join(covered_legs)}) Total mileage used = {total_used:.1f}")
    print(f"Total mileage wasted = {total_waste:.1f}")
    # 每个跑者的详情
    for idx in range(n_runners):
        p, t = res[idx]
        detail = {"Total": runs[idx], "Reminder": runs[idx], "Index": idx}
        used = 0.0
        for i in range(t):
            leg_num = p + i + 1
            detail[f"L{leg_num}"] = legs[p+i]
            used += legs[p+i]
        detail["Reminder"] = round(runs[idx] - used, 1)
        print(detail)
    return max_cnt

# 测试调用（起始赛段为第1个，对应索引0）
legs = [3.3, 4.2, 5.2, 3, 2.7, 4, 
        5.3, 4.5, 3, 5.8, 3.3, 4.9, 
        3.1, 3.2, 4, 3.5, 4.9, 2.3, 
        3.2, 4.6, 4.5, 4, 5.3, 5.9, 
        2.8, 1.9, 2.1, 3, 2.5, 5.6, 
        1.3, 4.6, 1.5, 1.2, 4.1, 8.1]
runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]
max_covered_legs(legs, runs, start_idx=0)

内容的提问来源于stack exchange，提问作者YuMei