I am looking for the optimum algorithm for the following:
- 10-15 players
- Each player has between 20 and 40 cards.
- Each card can have one of up to 200 possible characters, and a separate numerical rating (higher is better). Card's characters may duplicate between players, or in players hands. Ratings are highly unlikely to exactly duplicate, though they may be close.
I need to select 5 'active' cards from each players' hands to meet the following criteria:
- All characters must be unique - no duplicates in any of the 'active' cards of any of the players, or across all players.
- The total of the players' active cards' ratings must be as high as possible.
Right now I:
1) go through all players and find the highest rated card still available;
2) mark it as active for the player whose card it is; and
3) mark that character as used for all other players (so it doesn't get used again).
Repeat 1-3 until all players have 5 characters
This gives a pretty good result. But what if we had the following:
Player A:
Character 1, rating 100
Character 2, rating 99
Character 3, rating 98
Player B:
Character 1, rating 97
Character 4, rating 2
Character 5, rating 1
For the sake of the example, assume we only need two active cards per players.
If Player A uses Character 1 per my algorithm then:
- Player A: Character 1 + 2 = rating 199
- Player B: Character 4 + 5 = rating 3
- Total rating 201
Instead if Player A doesn't use Character 1 then:
- Player A: Character 2 + 3 = rating 197
- Player B: Character 1 + 4 = rating 99
- Total rating 296
So my algorithm does not produce the best team total rating.
Can anyone suggest a better algorithm, other than just brute force trying all the possible combinations to find the highest total rating? I wonder, for example, if there's something about finding the optimum ratings for each player and then adjusting them to avoid duplication with other players; or perhaps something completely different.