背包约束 python

Question

假设我有一个代表篮球运动员及其姓名、位置、成本和预计得分的元组列表，

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 背包可以做到这一点还是我需要切换到其他东西？

Answer 1

这称为“多项选择背包问题”。

您可以使用类似于 0/1 背包问题的动态规划解决方案的算法。

0/1背包问题的解法如下：（来自维基百科）

定义为重量小于或等于使用最多 的物品m[i, w]可以获得的最大值。 我们可以递归地定义如下：wi
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]。为了有效地做到这一点，我们可以使用一个表来存储以前的计算。

现在的扩展只是找到所有选择中的最大值。

对于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)