Algorithm to select Player with max points but with a given cost [closed]

Question

I need a algorithm that does the following:

In an NBA fantasy league, given:

1. each player's average point total
2. a price for each player
3. a salary cap

Select the optimal 9-player line-up.

To use an easy example, say there are only four players in the league, you have a $10,000 salary cap, and you want the optimal (meaning maximum points) 3-player lineup. Here are there average point totals and prices:

Lebron James: 30 points/game; $5,000
Kobe Bryant: 25 points/game; $3,500
Deron Williams: 20 points/game; $2,500
Shelvin Mack: 15 points/game; $2,000

The optimal lineup would be Bryant, Williams and Mack, which would cost $8,000 and score 60 points.

There is one further constraint: the program must select a certain number of players for each position (e.g., two point guards, two shooting guards, two small forwards, two power forwards and one center). This is what makes designing the program difficult.

Answer 1

First, it is easy to see that the generalization of the problem is NP-Hard, and is instantly reduceable from the Knapsack Problem:

Given a knapsack problem: weight=W, costs_of_items=C, weight_of_items=X, reduce the problem to this problem with no restrictions on the number of players (the generalization would be at most k players, where k is chosen by you).

So, we can conclude there is no known polynomial time solution to the problem.

But, we can develop a solution based on the knapsack pseudo-polynomial solution.
For simplicity, let's say we have restriction only on the number of small forwards (the principles of the answer can be applied to add more restrictions).

Then, the problem can be solved with the following recursive approach:

if i is not a forward, same as the original knapsack, while maintaining the #forwards
    f(i,points,forwards) = max {
                f(i-1,points-C[i],forwards)
                f(i-1,points,forwards)
                           }
if i is a forward:
    f(i,points,forwards) = max {
                //We used one of the forwards if we add this forward to the team
                f(i-1,points-C[i],forwards-1) 
                f(i-1,points,forwards)
                           }

The base will be all zeros where one of the dimensions is zero: f(0,_,_)=f(_,0,_)=0 (same as regular knapsack) and f(_,_,-1)=-infnity (invalid solution)

The answer will be f(2,W,n) (2 for the number of forwards, if it is different, that should be changed as well). W is the salary cap and n is the number of players.

The DP solution will fill the matrix representing the recursion bottom-up to get a pseudo-polynomial time solution (It is pseudo polynomial only if the restrictions are constant).

By repeating the process, and adding a dimension to each criteria, this problem will be solved optimally by the DP solution.

The complexity you will get is O(B^p * W * n) - where:
B is the "branch factor" - the number of players per position+1 (for the zero) in your case B=3.
W = salary cap
n = number of players to select from

---

If you find the optimal solution too time consuming, I'd suggest going for heuristic solutions, such as hill climbing or Genetic Algorithms, which will try to optimize the result as much as they can, but are not guaranteed to find a global maxima.

Answer 2

use dynamic programming can solve this easily. refer to this

let f[i][j] be the maximum points we can get using j dollars with the first i players, so

f[i][j] = max{

1. f[i - 1][j] //we don't choose the i-th player
2. f[i - 1][j - cost[i]] + point[i] //we choose him

}

finally f[TOTALPLAYER][MONEYCAP] is the answer.

the main idea is to determine whether to choose him or not for each player.

the array f[][] is just used to accelerate the search process.

btw, Chowlett is right.