Algorithm to auto-pick 11 players in a fantasy football lineup where the total price is near N

Question

I have a list of 500 floats.

I want to pick 11 numbers out of the list which when added together sum up to N and N is within a range X <= N <= Y

It's basically for a fantasy football game where we autopick 11 players in the persons lineup.

The total cost should be somewhere within a range rather than random.

One solution might be to continuously randomly pick 11 players until I get a total that fits within the range but i'm wondering if there is a more elegant approach?

Answer 1

Like the commenters pointed out, this is an NP-hard problem. However, if your data isn't too bad, the following should work pretty well:

picks[] := K numbers chosen at random from the population
While sum(picks) is not in the allowable range
  if sum(picks) < MinRange
    select an element p from picks at random
    let subpop := elements in population which are larger than p
    replace p with a random element from subpop
  if sum(picks) > MaxRange
    select an element p from picks at random
    let subpop := elements in population which are smaller than p
    replace p with a random element from subpop

This is pretty easy to code up, it will return a relatively random selection that satisfies the constraints, and it shouldn't take too long unless you really have a hard instance of the problem, in which case it's going to be very hard to find a solution using any algorithm.

If you want to speed up the algorithm, then you can choose the element p to be the smallest/largest element from picks each time through. This should make the algorithm go faster, but it will also result in a less "random" selection of picks.