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?