Ideas for optimization algorithm for Fantasy Football

So, this is a bit different than standard fantasy football. Wh开发者_JS百科at I have is a list of players, their average "points per game" (PPG) and their salary. I want to maximize points per game under the constraint that my team does not exceed a salary cap. A team consists of 1 QB, 1 TE, 3 WRs, and 2 RBs. So, if we have 15 of each position we have 15X15 X(15 c 3)X(15 c 2) = 10749375 possible teams.

Pretty computationally complex. I can use a bit of branch and bound i.e. once a team has surpassed the salary cap I can trim the tree, but even with that the algorithm is still pretty slow. I tried another option where I used a "genetic algorithm" i.e. made 10 random teams, picked the best one and "mutated" it (randomly changing some of the players) into another 10 teams and then picked of those and then looped through a bunch of times until the points per game of the "best team" stopped getting better.

There must be a better way to do this. I'm not a computer scientist and I've only taken an intro course in algorithmics. Programmers - what are your thoughts? I have a feeling that some sort of application of dynamic programming could help.

Thanks

---

I think a genetic algorithm, intelligently implemented, will yield an acceptable result for you. You might want to use a metric like points per salary dollar rather than straight PPG to decide the best team. This way you are inherently measuring value added. Also, you should consider running the full algorithm/mutation to satisfactory completion numerous times so that you can identity what players consistently show up in the final outcomes. These players then should be valued above others.

Of course the problem with the genetc approach Is that you need a good mutation algorithm and that is highly personal for how you want to implement it.

---

Take i as the current number of players out of n players and j to be the current remaining salary that is left. Take m[i, j] to be the dynamic set of solutions.

Then m[i, 0] = 0, m[0, j] = 0
and

m[i, j] = m[i - 1, j] if salary for player i is greater than j

else

m[i, j] = max ( m[i - 1, j], m[i - 1, j - salary of player i] + PPG of player i)

Sorry that I don't know R but I'm good with algorithms so I hope this helps.

A further optimization you can make is that you really only need 2 rows of m[i, j] because the DP solution only uses the current row and the last row (you can save memory this way)

---

First of all, the variation you have provided should not be right. Best way to build team is limit positions by limited plus there is absolutely no sense of moving 3 similar positions players between themselves.

Christian Ronaldo, Suarez and Messi will give you the equal sum of fantasy points in any line-up, like: Christian Ronaldo, Suarez and Messi or Suarez, Christian Ronaldo and Messi or Messi, Suarez, Ronaldo

First step - simplify the variation possibility. Next step - calculate the average price, and build the team one by one by adding player with lower salary but higher price. When reach salary limit, remove expensive one and add cheaper but with same fantasy points - and so on. Don't build the variation, value the weight of each player by combination of salary and fantasy points.

---

Does this help? It sets up the constraints and maximises points.

You could adapt to get data out of excel

http://pena.lt/y/2014/07/24/mathematically-optimising-fantasy-football-teams 14/07/24/mathematically-optimising-fantasy-football-teams