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 ?