Geek Answers Handbook

The player selection algorithm with maximum points, but with a given value

I need an algorithm that does the following:

In the NBA Fantasy League, given:

  • average score of each player
  • price for each player
  • salary amount

Choose the optimal composition of 9 players.

To use a simple example, let's say that there are only four players in your league, you have a limit of $ 10,000 and you want an optimal (keeping in mind the maximum scores) 3-game roster. Here are the average totals and prices:

LeBron James: 30 points / game; $ 5,000
Kobe Bryant: 25 points / game; $ 3,500
Deron Williams: 20 points / game; $ 2500
Shelvin Mack: 15 points / game; $ 2,000

The optimal composition would be Bryant, Williams and Mack, who would cost $ 8,000 and scored 60 points.

There is another limitation: the program must choose a certain number of players for each position (for example, two defense points, two shooters, two small forward, two forward forces and one center). This makes it difficult to design a program.

+6
source share
2 answers

Firstly, it is easy to see that the generalization of the NP-Hard problem is instantly reduced with the Backpack problem :

Given the backpack problem: weight=W, costs_of_items=C, weight_of_items=X , reduce the problem to this problem without limiting the number of players (the generalization will be no more than k players, where k chosen by you).

So, we can conclude that there is no known polynomial solution to the time problem.

But we can develop a solution based on a backpack pseudo-polynomial solution . For simplicity, suppose that we have a restriction only on the number of small forward ones (the principles of the answer can be applied to add additional restrictions).

Then the problem can be solved using the following recursive approach:

 if i is not a forward, same as the original knapsack, while maintaining the #forwards f(i,points,forwards) = max { f(i-1,points-C[i],forwards) f(i-1,points,forwards) } if i is a forward: f(i,points,forwards) = max { //We used one of the forwards if we add this forward to the team f(i-1,points-C[i],forwards-1) f(i-1,points,forwards) }

The base will be all zeros, where one of the dimensions is zero: f(0,_,_)=f(_,0,_)=0 (the same as a normal backpack) and f(_,_,-1)=-infnity (invalid solution)

The answer will be f(2,W,n) (2 for the number of forwards, if different, and this should be changed). W is the salary limit, and n is the number of players.

The DP solution will populate the matrix representing the recursion from the bottom up to get a pseudo-polynomial temporary solution (this is a pseudo-polynomial only if the constraints are constant).

By repeating the process and adding a measurement to each criterion , this problem will be optimally solved by the DP solution.

The difficulty you get is O(B^p * W * n) - where:
B is the "branching coefficient" - the number of players in each position + 1 (for zero) in your case B=3 .
W = salary
n = number of players to choose from

If you find the optimal solution is too time-consuming, I would suggest switching to heuristic solutions , such as climbing a hill or Genetic algorithms , which will try to optimize the result as much as possible, but do not guarantee to find global maximums.

+4
source

Using dynamic programming can solve this easily. refer to this

let f[i][j] be the maximum points that we can get with j dollars with the first i players, therefore

f [i] [j] = max {

  • f [i - 1] [j] // we do not select the i-th player
  • f [i - 1] [j - cost [i]] + point [i] // we select it

}

finally f[TOTALPLAYER][MONEYCAP] - the answer.

The basic idea is to determine whether or not to choose it for each player.

the array f[][] used only to speed up the search process.

btw, chowlett is right.

+1
source

More articles:


All Articles