3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ You should look up solutions to the KNAPSACK problem. It's not identical but it's very close and will give you lots of ideas. The main applicable technique is likely to be dynamic programming. $\endgroup$
    – David Richerby
    Nov 1, 2015 at 15:20
  • $\begingroup$ I've had a look at that, and I'm not sure how to draw the parallel. In particular, the Knapsack problem has no polynomial time solution, whereas this one does (the brute force method). I will dig a bit deeper, though. $\endgroup$
    – KBriggs
    Nov 1, 2015 at 15:47
  • $\begingroup$ Knapsack's also polytime if you have a fixed constant bound on how many items you can include. $\endgroup$
    – David Richerby
    Nov 1, 2015 at 18:08
  • $\begingroup$ it appears to me if you have a fixed budget for each position, its identical to the knapsack problem, or a series of knapsack problems. also, everyone else other than poster commenting is aware of this, but Knapsack is a classic NP complete problem (iirc, one of the earliest proven so by Karp). in other words, theres no efficient solution unless P=NP. also, there might be scientific literature on this general question of fantasy football code, there is almost surely not a unique way to do it; would you be interested in refs? $\endgroup$
    – vzn
    Nov 2, 2015 at 3:28
  • $\begingroup$ I would be very interested in references. I have been doing some searching myself, and it seems that good heuristic solutions are possible that are quite efficient, as well. $\endgroup$
    – KBriggs
    Nov 2, 2015 at 4:02

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I will have to pick a simple smaller problem (2 positions with a few players in each) and write it out by hand to understand exactly what is going on here, but this looks promising. I will see about getting this done in the next few days. I guess s here just runs over possible salary caps? For the problem I have salaries are multiples of 100, so s would range from 100 to s_max by 100, and the best team would be the team that generates T[9,s_max]? I would have to associate and keep track of the team that generated each cell of the table as well. $\endgroup$
    – KBriggs
    Nov 2, 2015 at 2:17
  • $\begingroup$ an english description/ explanation of the recurrence relation and its rationale is in order otherwise its a "black box" $\endgroup$
    – vzn
    Nov 2, 2015 at 3:23
  • $\begingroup$ An English description would be most welcome, but I think I get the idea. $\endgroup$
    – KBriggs
    Nov 2, 2015 at 4:05
  • $\begingroup$ @KBriggs, yes, what you write is correct: you are understanding correctly. $\endgroup$
    – D.W. ♦
    Nov 2, 2015 at 5:54
  • $\begingroup$ @D.W. Actually I am not so sure this will work directly. This is not quite the vanilla Knapsack problem because we have subtypes of items and we have a quota for each subtype. Because of the requirement that we have a quota of subtypes of items, I think the solution you have given will depend on the order in which positions are assigned to rows, no? $\endgroup$
    – KBriggs
    Nov 3, 2015 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.