Contained optimal combination of inputs

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)?

It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.

StackExchange Computer Science Q#68061, answer score: 3