假设我有一个元组列表,代表篮球运动员及其姓名、位置、成本和预计得分,
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)
]
假设所有名称、成本和投影点都是可变的。
我有一个传统的背包问题,他们可以根据给定的重量对背包进行分类和包装。但这不占位置。
我想知道是否有一种方法可以编辑背包代码以仅包含每个位置中的一个,即(pg、sg、sf、pf、c)。
传统的 0/1 背包可以做到这一点,还是我需要换成其他东西?
最佳答案
这被称为“多项选择背包问题”。
对于 0/1 背包问题,您可以使用类似于动态规划解决方案的算法。
0/1背包问题的解如下:(来自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.
现在扩展只是为了找到所有选择中的最大值。
对于 n
个玩家可作为某些位置 i
的选择(c_i_j
是选择 j
的成本和 p_i_j
是点),我们有:
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)
所以,假设我们有:
Name Position Cost Points
Player1 PG 15 5
Player2 PG 20 10
Player3 SG 9 7
Player4 SG 8 6
然后我们有 2 个位置“PG”和“SG”,每个位置将有 2 个选择。
因此,对于位置“PG”(在 i=1
),我们将有:
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)
对于位置“SG”(在 i=2
),我们将有:
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)
关于python - 背包约束python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19389931/