CODEWITHSUNDEEP
algorithmcombinations
user1657825
user1657825

Reputation: 49

Algo. to pick best combination out of possibilities

I have to solve following problem, basically it is to pick a best combination out of possible ones (huge) - I have to pick a best soccer team out of possible players, each player is given a score, I have to pick a team which has highest total score out of selected players.

There is a restriction on the players that I can select: at maximum I can only pick N (=2 for instance) players from a club. E.g if I have picked G1 (from Chelsea) as goalkeeper, then only 1 slot left for Chelsea.

Say I have to pick a best formation of 1-4-4-2

Goalkeeper (1): g1, g2, g3, g4 ... (name of players in this position, and their scores are correspondingly gc1, gc2, gc3, gc4 ...)

Defenders (4): d1, d2, d3, ...

Midfielders (4): m1, m2, m3, ...

Strikers (2): s1, s2, s3, s4, ...

What algorithm can I use here? I am looking at the so-called Hungarian algo: http://en.wikipedia.org/wiki/Hungarian_algorithm

But it looks complicated and not sure if good for this case.

Any help would be much appreciated.

Best,

Upvotes: 1

Views: 1268

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

It's solvable via the minimum-cost flow problem, a generalization of the problem that the Hungarian algorithm solves.

Create a network with (1) one node per club (2) one node per player (3) one node per open position. Each club node sources two units of flow, and each open-position node sinks units equal to however many players of that position are needed. There are club-to-player arcs for each such relationship, with capacity one and cost zero. There are player-to-open-position arcs also, with capacity one and cost equal to minus that player's value at that position (multiple such arcs involving one player are possible if there are "flex" spots as in fantasy American football).

Find an min-cost integral flow of value eleven. Each player is used as transit for either zero or one unit of flow. The best team is comprised of the latter.

Upvotes: 2

Related Questions