I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined score (i.e. a fantasy football formation) within a $50,000 budget, where a lineup must consist of the following formation:
- Goalkeeper x1
- Defender x2
- Midfielder x2
- Forward x2
- Utility x1 (can be any position apart from GK)
Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one not already used non-goalkeeper as a "utility" (from the 100 - 18 = 82).
Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.
What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment (i.e. there are trillions of possible combinations)?