This is called the "multiple-choice knapsack problem".
You can use an algorithm similar to the dynamic programming solution for the 0/1 knapsack problem.
The 0/1 knapsack problem's solution is as follows: (from Wikipedia)
Define
m[i, w]
to be the maximum value that can be attained with weight less than or equal tow
using items up toi
.
We can definem[i, w]
recursively as follows:m[i, w] = m[i-1, w] if w_i > w (new item is more than current weight limit) m[i, w] = max(m[i-1, w], m[i-1, w-w_i] + v_i) if w_i <= w.
The solution can then be found by calculating
m[n,W]
. To do this efficiently we can use a table to store previous computations.
Now the extension is just to find the maximum of all choices instead.
For n
players available as choices for some position i
(with c_i_j
being the cost of choice j
and p_i_j
being the points), we'd have:
m[i, c] = max(m[i-1, c],
m[i-1, c-c_i_1] + p_i_1 if c_i_1 <= c, otherwise 0,
m[i-1, c-c_i_2] + p_i_2 if c_i_2 <= c, otherwise 0,
...
m[i-1, c-c_i_n] + p_i_n if c_i_n <= c, otherwise 0)
So, say we have:
Name Position Cost Points
Player1 PG 15 5
Player2 PG 20 10
Player3 SG 9 7
Player4 SG 8 6
Then we'd have 2 positions "PG" and "SG" and each position will have 2 choices.
Thus, for position "PG" (at i=1
), we'll have:
m[i, c] = max(m[i-1, c],
m[i-1, c-15] + 5 if 15 <= c, otherwise 0,
m[i-1, c-20] + 10 if 20 <= c, otherwise 0)
And for position "SG" (at i=2
), we'll have:
m[i, c] = max(m[i-1, c],
m[i-1, c-9] + 7 if 9 <= c, otherwise 0,
m[i-1, c-8] + 6 if 8 <= c, otherwise 0)