使用Python Pandas构建无重复ID的最优11人球员团队

核心问题拆解 #

这是一个带双重约束的最大化问题：

• 约束1：11个位置（对应不同statut）各选1名球员
• 约束2：所有选中球员的id不重复
• 目标：选中球员的niveau总和最大（等价于平均水平最高）

暴力枚举所有组合在数据量大时完全不可行，用整数规划是获取全局最优解的可靠方案。

具体实现（Python + Pulp库） #

1. 安装依赖 #

pip install pulp pandas

2. 代码实现 #

假设你的数据集存储在df中，包含id、statut、niveau三列：

import pandas as pd
import pulp

# 读取数据集（替换为你的数据路径）
# df = pd.read_csv("your_data.csv")

# 验证statut数量为11（对应11个团队位置）
statuts = df["statut"].unique()
assert len(statuts) == 11, "statut数量必须为11，对应11个团队位置"

# 提取所有唯一球员ID
player_ids = df["id"].unique()

# 创建决策变量：x[id, statut] = 1 表示该球员在对应位置被选中，否则为0
x = pulp.LpVariable.dicts(
    "selection",
    [(pid, st) for pid in player_ids for st in statuts if not df[(df["id"] == pid) & (df["statut"] == st)].empty],
    cat="Binary"
)

# 定义最大化问题
prob = pulp.LpProblem("OptimalTeam", pulp.LpMaximize)

# 目标函数：最大化选中球员的niveau总和
prob += pulp.lpSum([
    x[(pid, st)] * df[(df["id"] == pid) & (df["statut"] == st)]["niveau"].values[0]
    for (pid, st) in x
])

# 约束1：每个位置必须且只能选1名球员
for st in statuts:
    prob += pulp.lpSum([x[(pid, st)] for pid in player_ids if (pid, st) in x]) == 1

# 约束2：每个球员只能被选中一次
for pid in player_ids:
    prob += pulp.lpSum([x[(pid, st)] for st in statuts if (pid, st) in x]) <= 1

# 求解问题（关闭日志输出）
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# 提取并整理结果
selected = []
for (pid, st) in x:
    if pulp.value(x[(pid, st)]) == 1:
        niveau = df[(df["id"] == pid) & (df["statut"] == st)]["niveau"].values[0]
        selected.append({"id": pid, "statut": st, "niveau": niveau})

result_df = pd.DataFrame(selected)
print("最优团队：")
print(result_df)
print(f"平均niveau：{result_df['niveau'].mean():.2f}")

方案优势 #

• 自动处理id重复问题，通过约束强制每个球员仅出现一次
• 遍历所有满足约束的组合，确保得到全局最优解，而非局部最优
• 适配任意规模的球员数据，只要每个位置有可选球员即可

快速近似方案（贪心算法） #

如果数据量极大导致整数规划求解缓慢，可使用贪心策略快速获取近似解（无法保证最优）：

# 贪心算法实现
result_greedy = []
used_ids = set()

# 按位置分组，每组按niveau降序排序
grouped = df.groupby("statut").apply(lambda g: g.sort_values("niveau", ascending=False)).reset_index(drop=True)

for st in statuts:
    # 选取当前位置未被使用的最高niveau球员
    for _, row in grouped[grouped["statut"] == st].iterrows():
        if row["id"] not in used_ids:
            result_greedy.append(row)
            used_ids.add(row["id"])
            break

result_greedy_df = pd.DataFrame(result_greedy)
print("贪心算法结果：")
print(result_greedy_df)
print(f"平均niveau：{result_greedy_df['niveau'].mean():.2f}")

注：贪心算法可能因优先选择单位置顶级球员，占用其他位置更优球员名额，导致最终总和低于整数规划结果。

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