向背包算法添加类别约束

Question

我试图实施背包算法玩幻想篮球。我写了一个传统0/1背包解算器，它为每个玩家提供成对的价值和权重（价格），并输出组合薪酬低于工资上限的玩家最有价值的组合。但是，幻想竞赛强制你必须根据玩家的位置来组成你的8人阵容 - 即你的阵容必须由1名控卫，1名得分后卫，1名小前锋，1名大前锋， 1个中锋，1名得分后卫或控卫，1名小前锋或大前锋，以及1名任意位置的球员。

我在寻找如何扩展传统动态编程背包算法以包含这些约束的建议。

Answer 1

将另一个维度添加到您的阵列中，标记您填充的阵容中的哪个位置。

Answer 2

正如索林所说，你需要DP中的另一个状态来跟踪填充的位置。

使用您的DP，其中第i个位表示第i个角色是否已经采取的第三状态的位掩码。例如，255 =（11111111），这意味着每个可能的角色都被采用。

这是可行的，因为角色数量只有八个。另外，每个角色只需要一名玩家。因此，第三个状态需要一个相对较小的数组（2^8 = 256）。理论上，你可以使用更大的基地，而不是使用二进制基地。通常，您的第三个状态需要大小排列，其中b =每个角色的玩家+1和r =角色，但内存使用量可能很大。