user2758113 - 2 years ago 202
Python Question

# Knapsack constraint python

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?

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)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download