algorithm - 最大数量 "Teams"

Question

我有一个团队的定义。我需要根据人员列表(及其适用的位置)找到我可以获得的最大数量的团队，因为一旦一个人被“用于”一个位置，他们就不能再次使用。

简化示例:

**Team Requirements**
Slot A: 2 People
Slot B: 1 Person
Slot C: 1 Person

**People And Which Slots Are Applicable**
Person 1: A
Person 2: A,C
Person 3: A,B
Person 4: B
Person 5: A,B
Person 6: C
Person 7: C
Person 8: A

可能的答案

Team 1
A: P1, P8
B: P4
C: P6

Team 2
A: P2, P3
B: P5
C: P7

对于我的现实世界问题，我有多个槽(每个团队 1-10 个)和 1-1000 人，每个人最多有 20 个槽。

有谁能推荐适合这类群优化问题的算法吗？

Answer 1

这可以通过找到 Maximum Cardinality Bipartite Matching 来解决。在一系列图表中的每一个中，总体时间为 O(n^2.5 log n)。

为此，首先将每个插槽 type 转换为一组适当数量的不同插槽，以便我们最终得到插槽 A1、A2、B、C。最终解决方案将分配一个人到特定团队中的特定位置(例如，人 3 到团队 1 中的位置 A2)，但我们可以简单地忘记“2”(以及团队的顺序，这同样是纯人为的)。

首先计算团队数量的乐观估计 k:RoundDown(n/4) 就可以了，因为每个团队使用 4 个人，所以我们不能有比这更多的团队。现在在二分图的一部分中创建 4k 个顶点——也就是说，每个 k 个潜在团队中的 4 个槽中的每一个都有一个顶点:A1_1、A2_1、B_1、C_1、A1_2、A2_2、B_2、C_2、.. ., A1_k, A2_k, B_k, C_k。在二分图的另一部分，为每个人制作一个顶点。最后，将每个人顶点与允许他们填充的所有槽顶点连接起来:如果一个人 x 可以占据插槽 A 或 C，则他们应该通过一条边连接到以“A”或“C”开头的每个插槽(对于 8 人的示例，这将是 6 条边)。

然后，解决这个图上的 MCBM 问题，例如在 O(n^2.5) 时间内使用 Hopcroft-Karp algorithm .结果将是边缘的一个子集，可以解释为将每个人分配到团队中的最多一个位置，并且最多用一个人填充团队中的每个位置。如果这导致每个插槽都被填满，万岁!我们拥有尽可能多的团队。否则，如果有一些团队名额未被任何人填补，请减少团队数量并重试。 (您可以每次将团队数量减少 1，这会导致线性数量的 MCBM 问题需要解决——但您可以通过二分搜索来节省时间。这意味着首先将团队数量减半，并且此后将团队数量减少或增加到之前数量的一半，当一些团队有空缺职位时减少，当没有职位空缺时增加，直到收敛。)