问题描述
可以说我有元组重新presenting篮球运动员和他们的名字，位置，成本，和他们的投影点的列表，
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.
我有一个传统的背包问题的工作，就可以进行排序，并打包基于给定重量背包。但是，这并不占位置。
我不知道是否有一种方法可以编辑背包code只包括一个每一个位置，即，（PG，SG，SF，PF，C）。
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).
能否传统的0/1背包做或做我需要切换到别的东西？
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".
您可以使用一种算法类似的0/1背包问题的动态规划的解决方案。
You can use an algorithm similar to the dynamic programming solution for the 0/1 knapsack problem.
在0/1背包问题的解决方法如下：（从维基百科）
The 0/1 knapsack problem's solution is as follows: (from Wikipedia)
定义 M [I，W] 是可以达到体重小于或等于是W 使用项目达我。
我们可以定义 M [I，W] 递归如下：
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.
该解决方案就可以通过计算发现 M [N，W] 。要做到这一点效率，我们可以使用一个表来存储previous计算。
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.
有关 N 可作为选择的球员一些位置我（用 c_i_j 是选择的成本Ĵ和 p_i_j 作为点），我们就会有：
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
然后我们就会有2个位置PG和SG，每个位置都会有2个选择。
Then we'd have 2 positions "PG" and "SG" and each position will have 2 choices.
因此，对于位置PG（在 I = 1 ），我们将有：
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)
和卡位神光（在 I = 2 ），我们将有：
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)
这篇关于背包约束蟒蛇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！