Knapsack constraint python

Question

Lets say I have a list of tuples representing basketball players and their name, position, cost, and their projected points,

listOfPlayers = [
                 ("Player1","PG",Cost,projectedPoints),
                 ("Player2","PG",Cost,projectedPoints),
                 ("Player3","SG",Cost,projectedPoints),
                 ("Player4","SG",Cost,projectedPoints),
                 ("Player5","SF",Cost,projectedPoints),
                 ("Player6","SF",Cost,projectedPoints),
                 ("Player7","PF",Cost,projectedPoints),
                 ("Player8","PF",Cost,projectedPoints),
                 ("Player9","C",Cost,projectedPoints),
                 ("Player10","C",Cost,projectedPoints) 
                ]

Assume all of the names, costs, and projected points are variable.

I have a traditional knapsack problem working, they can sort and pack a knapsack based on a given weight. But this does not account for the positions.
I was wondering if there is a way to edit the knapsack code to only include one of every position, i.e., (pg, sg, sf, pf, c).

Can a traditional 0/1 knapsack do this or do i need to switch to something else?

Answer 1

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 to w using items up to i.
We can define m[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)

Answer 2

First of all, excellent answer by Dukeling. I don't have the privilege of commenting, so I am writing an answer. This is in fact a "Multiple-Choice Knapsack Problem". I implemented one of this kind of problem and ran it in Online Judge, where it was executed successfully. The only problem with Dukeling's algorithm is that it will not take into consideration that at least one item of previous set of items. So, from above :

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)`

This would only work for at most one of a kind. If you add a little check for zero, it will be perfect for exactly one item of each type, if for i=1 ("PG") :

m[i, c] = max(m[i-1, c],
          m[i-1, c-15] + 5    if 15 <= c and  m[i-1, c-15] != 0, otherwise 0,
          m[i-1, c-20] + 10   if 20 <= c and  m[i-1, c-20] != 0, otherwise 0)

For i=2 ("SG") :

m[i, c] = max(m[i-1, c],
          m[i-1, c-9] + 7    if 9 <= c and m[i-1, c-9] != 0, otherwise 0,
          m[i-1, c-8] + 6    if 8 <= c and m[i-1, c-8] != 0, otherwise 0)

And, so on.