两队对抗选手选派最优解求解算法咨询

你的思路核心问题 #

你的贪心思路是错误的，问题出在A队选手的选择逻辑上：

• 你直接按所有A选手的行和大小选前5名、默认行和最高的当队长，没有考虑B队会针对性选择克制阵容。部分行和高的A选手可能存在明显的被克制短板，B队可以轻松选出对阵他得分极低的选手拉低总分，反而不如选行和稍低但没有明显短板的组合。
• B队的选择逻辑本身是正确的：对给定的A队阵容，B队确实要选对阵A队总得分最低的5名选手，且让得分最低的当队长（权重翻倍），使得总对阵分最小。

正确的高效解法 #

这个问题完全不需要O(n!)级别的暴力枚举，实际可以在非常低的复杂度下求解：

核心逻辑 #

这个是典型的极小极大博弈问题：

1. A队先选5人+指定队长，等价于给每个A选手分配权重w_a：选中的队长权重为2，其余4名选中选手权重为1，未选中选手权重为0，权重总和为6。
2. 对给定的A队权重，每个B选手的对阵总得分s_i = sum(w_a[a] * matrix[a][i] 对所有A选手a)，B队要让总对阵分最小，必然选s_i最小的5个选手，且让最小的s_i对应选手当队长（权重2），此时B队的最优总得分就是：排序后的前5个最小s_i[0]*2 + s_i[1] + s_i[2] + s_i[3] + s_i[4]。
3. A队的目标就是遍历所有可能的w_a组合，找到B队最优应对下总得分最高的那组即可。

复杂度计算 #

A队的所有可能组合数为 C(a,5) * 5：先从a个选手里选5个，再从5个里指定1个当队长：

• 如果a=11：C(11,5)*5 = 462 * 5 = 2310 种组合
• 如果a=20：C(20,5)*5 = 15504 *5 = 77520 种组合
  每种组合处理仅需要O(b)计算s_i + O(b log b)排序，就算a=20、b=20，总计算量也完全在可接受范围内，属于非常高效的解法。

示例代码片段（Python） #

import itertools

a = int(input())
b = int(input())
matrix = [list(map(int, input().split())) for _ in range(a)]

max_total = -float('inf')
selected_A_set = set()

# 遍历所有A队选5人的组合
for selected_A in itertools.combinations(range(a), 5):
    selected_A_set.clear()
    selected_A_set.update(selected_A)
    # 遍历每个选中的A选手当队长
    for captain_A in selected_A:
        # 计算每个B选手的s_i
        s_B = [0]*b
        for a_idx in selected_A_set:
            weight = 2 if a_idx == captain_A else 1
            for b_idx in range(b):
                s_B[b_idx] += weight * matrix[a_idx][b_idx]
        # B队选最优：s升序取前5，最小的当队长
        s_B.sort()
        b_total = s_B[0]*2 + s_B[1] + s_B[2] + s_B[3] + s_B[4]
        # 更新最大总分
        if b_total > max_total:
            max_total = b_total

print(max_total)

上述代码可以直接通过你给出的示例输入，输出结果为1282。

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