myaw's blog

Choose the perfect team
By myaw, history, 4 years ago, In English

Hi cf,

I'm trying to solve this problem:

You have a budget B and you want to form a team of 11 players such as it has:

  • 1 goalkeeper
  • At least 3 defenders and at most 5.
  • At least 3 midfielders and at most 5.
  • At least 1 attackers and at most 3.

There's a list of players (max 50) to choose from, with each player has a:

  • type: goalkeeper, defender, midfilder or attacker
  • cost: price of the player
  • points: represent how good the player is

What is the maximum of total points that we can get from a team that fulfill the conditions without exceeding the budget B

it is guaranteed that the maximum number of players per type in the input doesn't ecxeed 15.

Example of input:

20
Defender 22 7
Attacker 40 9
...

Constraints

N (nomber of input players) <= 50

Cost of a player is an integer <= 10

budget <= 100

Each type in the input will not exceed 15 (ex: at most 15 defender)

All I can think of is recurssive dp with bitmask dp(chossenGkmask, chossenDefmask, chosseMidmask, chossenAttmask, totalCoast)

Is there a better approach ?

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Problem link?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Constraints?

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

You can just build a knapsack dp[i][j][w][x][y][z], which is the maximum number of points we can get after processing the i-th player, spending j coins, with w goalkeepers, x defenders, y midfielders, and z attackers. If you need to output the optimal team, you can do this too, by retracing your steps.

→ Reply