Best algorithm to find highest possible number of points from unique cards

Question

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:

1. All characters must be unique - no duplicates in any of the 'active' cards of any of the players, or across all players.
2. 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.

Answer 1

I don't know why D.W. believes this is NP-complete, because it isn't. In order to solve the problem let us first change it (without loss of generality):

1. For each player only keep the highest rated card of a particular character. The lesser rated card(s) will never be part of the optimal solution.

2. For each player add a virtual card to their hand for each character they're missing, with rating -1 (or -inf if ratings can be negative). This ensures this card is never picked, but normalizes the problem.

3. Duplicate each player 5 times.

4. Negate ratings to turn them into costs.

Let's assume we had $p$ players and $c$ characters in the roster. After this transformation we have a typical assignment problem, where we have $5p$ workers and $c$ tasks. Viewing cards as tasks and 'player hand slots' as workers, we have an associated cost $c(w, t)$ for a worker $w$ and task $t$ combination, and our goal is to minimize the total cost.