如何用递归CTE构建无重复球员的最低薪资排球阵容？

需求概述 #

需要编写SQL查询，为欧洲排球联赛的球队筛选薪资最低的6人合规阵容，要求：

• 阵容必须覆盖全部6个指定位置：Libero、Opposite、Setter、Middle、Outside Hitter、Defensive Specialist
• 同一球员不能重复入选（即使该球员可胜任多个位置）
• 球队至少有10名球员，需通过合理分配多位置球员的位置，实现总薪资最低

示例球员数据 #

Player    Position               Salary
----------------------------------------
Player A  Libero                 100
Player A  Defensive Specialist   100
Player B  Opposite               200
Player C  Middle                 150
Player D  Outside Hitter         175
Player D  Opposite               150
Player E  Setter                 100
Player F  Setter                 150
Player G  Middle                 125
Player G  Opposite               100
Player H  Libero                 75
Player I  Outside Hitter         150
Player J  Defensive Specialist   200

现有方案的问题 #

你最初的思路是枚举所有可能的6人组合再排序，但球队规模较大时这种方法效率极低；当前的查询仅能按位置取首条记录，完全没有处理球员重复入选的问题：

WITH Squads AS
(
    SELECT PlayerName, Salary, Position,
        ROW_NUMBER() OVER (PARTITION BY Position ORDER BY Position) AS RowNumber
    FROM Players
)
SELECT * FROM Squads WHERE RowNumber = 1 ORDER BY Position, Salary DESC, PlayerName

高效解决方案：递归CTE逐步构建阵容 #

核心思路是缩小候选范围+逐步构建合规阵容，只考虑每个位置薪资较低的球员（避免无效的高薪组合），同时用递归CTE逐个添加位置，确保球员不重复，最终筛选出总薪资最低的阵容。

步骤说明 #

1. 筛选位置候选：为每个位置保留薪资最低的N名球员（比如前3名，可根据球队规模调整），大幅减少后续计算量
2. 递归构建阵容：从第一个位置开始，逐步添加未覆盖位置的球员，记录已选球员、覆盖位置和当前总薪资
3. 筛选最优结果：当阵容覆盖全部6个位置时，停止递归，按总薪资排序取最小值

完整SQL代码（以SQL Server为例） #

WITH PositionCandidates AS (
    -- 为每个位置筛选薪资最低的3名球员，可调整N值平衡效率与准确性
    SELECT 
        Player, Position, Salary,
        ROW_NUMBER() OVER (PARTITION BY Position ORDER BY Salary ASC) AS rn
    FROM Players
    WHERE rn <= 3
),
RecursiveSquads AS (
    -- 递归起始：先获取Libero位置的所有候选
    SELECT 
        CAST(Player AS VARCHAR(MAX)) AS SelectedPlayers,
        CAST(Position AS VARCHAR(MAX)) AS CoveredPositions,
        Salary AS TotalSalary,
        1 AS PositionCount
    FROM PositionCandidates
    WHERE Position = 'Libero'
    UNION ALL
    -- 递归步骤：添加下一个未覆盖位置的球员，确保未重复选择
    SELECT 
        rs.SelectedPlayers + ', ' + pc.Player,
        rs.CoveredPositions + ', ' + pc.Position,
        rs.TotalSalary + pc.Salary,
        rs.PositionCount + 1
    FROM RecursiveSquads rs
    JOIN PositionCandidates pc 
        ON pc.Position NOT IN (SELECT value FROM STRING_SPLIT(rs.CoveredPositions, ', '))
        AND pc.Player NOT IN (SELECT value FROM STRING_SPLIT(rs.SelectedPlayers, ', '))
    WHERE rs.PositionCount < 6
),
FullSquads AS (
    -- 筛选出覆盖全部6个位置的阵容，并按薪资排序
    SELECT 
        SelectedPlayers,
        CoveredPositions,
        TotalSalary,
        ROW_NUMBER() OVER (ORDER BY TotalSalary ASC) AS SquadRank
    FROM RecursiveSquads
    WHERE PositionCount = 6
)
-- 输出薪资最低的阵容，还原实际薪资（示例中薪资已除以1000）
SELECT 
    SelectedPlayers AS 入选球员,
    CoveredPositions AS 覆盖位置,
    TotalSalary * 1000 AS 总薪资(欧元)
FROM FullSquads
WHERE SquadRank = 1;

优化提示 #

• 调整PositionCandidates中的rn <= 3：如果某个位置低薪球员较多，可适当增大N值避免遗漏最优解；球队规模大时减小N值提升效率
• 字符串拆分适配：如果使用PostgreSQL，替换STRING_SPLIT为string_to_array；MySQL可用SUBSTRING_INDEX或自定义拆分函数
• 数组存储优化：部分数据库支持数组类型，用数组存储已选球员和覆盖位置，比字符串拆分更高效

替代方案：笛卡尔积筛选（适用于小数据集） #

如果球队规模较小，也可以用多表连接枚举所有位置组合，再筛选无重复球员的阵容：

WITH AllCombinations AS (
    SELECT 
        p1.Player AS Libero, p1.Salary AS L_Sal,
        p2.Player AS Opposite, p2.Salary AS O_Sal,
        p3.Player AS Setter, p3.Salary AS S_Sal,
        p4.Player AS Middle, p4.Salary AS M_Sal,
        p5.Player AS Outside_Hitter, p5.Salary AS OH_Sal,
        p6.Player AS Defensive_Specialist, p6.Salary AS DS_Sal,
        p1.Salary + p2.Salary + p3.Salary + p4.Salary + p5.Salary + p6.Salary AS Total_Salary
    FROM Players p1
    JOIN Players p2 ON p2.Position = 'Opposite'
    JOIN Players p3 ON p3.Position = 'Setter'
    JOIN Players p4 ON p4.Position = 'Middle'
    JOIN Players p5 ON p5.Position = 'Outside Hitter'
    JOIN Players p6 ON p6.Position = 'Defensive Specialist'
    -- 确保所有球员不重复
    WHERE 
        p1.Player NOT IN (p2.Player, p3.Player, p4.Player, p5.Player, p6.Player)
        AND p2.Player NOT IN (p3.Player, p4.Player, p5.Player, p6.Player)
        AND p3.Player NOT IN (p4.Player, p5.Player, p6.Player)
        AND p4.Player NOT IN (p5.Player, p6.Player)
        AND p5.Player != p6.Player
)
SELECT TOP 1 * FROM AllCombinations ORDER BY Total_Salary ASC;

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