I need to build a sql query to find the least expensive squad (salary-wise) for teams in a European volleyball league.
For each team, the squad consists of 6 players. The entire team has 10 players (but could have more).
Positions are:
Here is a query result showing Players, Positions and Salaries. Note that some players can play multiple positions. Salaries are in Euros, and are divided by 1000 to make things simpler.
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
Since some players can fill multiple positions, I need weigh the benefit of moving them to another position to reduce the payroll, even if they are less expensive in the first position. For example, if a player can fill Libero and Defensive Specialist positions, and as a Libero they are less expensive than other Liberos on the team, as a Defensive Specialist, they may even make the squad less expensive than if they were in the Libero position.
My first instinct is to generate all possible 6-person squads with all of the players (making sure that the same player is not in the same squad twice) - then ordering by the sum of salaries. Doing this would find all combinations, and give me the least-expensive squad. But depending on the size of the team, this could be a very intensive task, so I wonder if there's a more efficient way.
I can find the first squad like this (though this doesn't check for duplicate player names in different positions):
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
I believe I would then want to add a UNION ALL or a CROSS APPLY in the CTE to recurse through all players and positions, making sure that each squad has a player in each of the 6 positions.
What's the best method to do this?
This answer stores the position data in a separate table, and then recursively iterates over each position ID, joining previously unselected players who are listed under that position to the result. The running salary is stored, along with the players currently chosen for the given squad:
with recursive cte(pid, position, player, players, salary) as (
select 2, p.position, p1.player pl1, p1.player, p1.salary
from positions p join players p1 on p1.position = p.position where p.id = 1
union all
select c.pid + 1, p.position, p1.player, c.players||','||p1.player, c.salary + p1.salary
from cte c join positions p on p.id = c.pid join players p1 on p1.position = p.position where not c.players ~ p1.player
),
final_team as (
select c.players, c.salary from cte c where c.pid = 7
)
select f.* from final_team f where f.salary = (select min(f1.salary) from final_team f1)