I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, and a salary cap, build the highest projected scoring NFL team that fits the salary cap. I am interested in finding an efficient way to do this.An NFL team consists of 1 QB, 1 TE, 1 K, 1 D, 3 WRs and 2 RBs. Each position has a varying number of potential players available, but for the sake of argument we can say that from an initial list of about 600 players total, we can safely eliminate most of them so that there are 5-15 players to choose from for each position. I have solved this problem with a brute force approach: I have a separate loop for each position, loop over all available players, and find the best team that fits the salary cap. This works, but having written a function containing 9 nested loops makes me feel dirty. To deal with a dataset with around 10 players in each position as options, it takes about 2 hours to finish. Past that, it would be too slow to be useful.Several websites out there do exactly this: For Example. However, if you reject a player from their lineup and recalculate, it takes less than a second to find a new optimized lineup. It was pointed out to me that it is possible that they are doing a pre-computation and storing all possible teams in a database, and simply searching through it in order to find new optimized lineups when someone tweaks things, but I am hoping that is not the case. So the question, finally: is there an efficient algorithm that guarantees an optimal solution, assuming that the best team mean maximizing the sum of projected points for the players on the team?
Optimizing NFL draft picks
algorithms;optimization;knapsack problems;program optimization
Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem.Basically, order the positions from 1 to 9.  You're going to fill in a two-dimensional table $T$, where $T[i,s]$ denotes the score of the highest-scoring team that fills in just the first $i$ positions and has a salary cap of $s$.  The key observation is: given the row $T[i-1,\cdot]$ of the table, you can compute $T[i,s]$ via a simple recurrence relation.  In particular,$$T[i,s] = \max \{ T[i-1,s-s_j] + p_j : j=1,2,3,\dots\},$$where $j$ ranges over the candidates for the $i$th position, $s_j$ is the salary of the $j$th candidate, and $p_j$ is the projected points generated by the $j$th candidate.   This lets you fill in the table, row by row.The running time is quadratic: proportional to the total salary for the team, times the number of positions.  There are two nested loops, rather than 9.