title: Python Roster optimizer
body: <p>I am trying to build a python program to optimize a fantasy sports roster.  I have looked into scipy and am throughly confused about how to tackle the problem.  The problem is to maximize the expected amount of points for a roster, constrained to one of each player position.  Additionally, each player has a salary, and the sum of all the players salaries is also constrained.  So in short, I would like to choose the combination of players to maximize the expected points, while not exceeding the salary cap.  </p>
  
  <p>I initially started to do this using nested loops, but it would take an extreme amount of time.</p>
  
  <p>Any ideas on how to approach this problem?</p>
  
  <p>Here is an example of the data, in a pandas dataframe.  </p>
  
  <pre><code>    Position    Name    Salary  AvgPointsPerGame
      0   PG  Russell Westbrook   13200   54.004
      1   SG  James Harden        11500   49.982
      2   PF  Anthony Davis       11200   49.594
      3   SF  LeBron James        10100   47.861
      4   PG  Chris Paul          9900    44.278
      5   C   DeMarcus Cousins    9600    49.477
      6   SF  Kevin Durant        9500    43.481
      7   PF  Blake Griffin       8900    41.705
      8   PF  LaMarcus Aldridge   8800    42.816
      9   PF  Pau Gasol           8700    42.250
      10  PG  John Wall           8600    41.722
      11  C   DeAndre Jordan      8300    37.342
      12  SG  Eric Bledsoe        8200    37.132
      .....
  </code></pre>
  
  <p>I am looking into the knapsack problem as suggested... any advice on modifying this code to 1)restrict the size of the bag to 6, and 2) limit each position to a maximum of 2 spots.  Thanks for the help.</p>
  
  <pre><code>def knapsack(items, limit):
  table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
  
  for j in xrange(1, len(items) + 1):
      pos, name, cost, val = items[j-1]
      for w in xrange(1, limit + 1):
          if cost &gt; w:
              table[j][w] = table[j-1][w]
          else:
              table[j][w] = max(table[j-1][w], table[j-1][w-cost] + val)
  
  result = []
  w = limit
  for j in range(len(items), 0, -1):
      was_added = table[j][w] != table[j-1][w]
  
      if was_added:
          pos, name, cost, val = items[j-1]
          result.append(items[j-1])
          w -= wt
  
  return result
  </code></pre>