根据员工偏好将员工分配到团队的算法
Algorithm to assign workers to teams based on workers preferences
我们有 N 名工人，他们应该被分配到 M 个团队之一。每个团队最多可以有 K 名工人。每个工作人员按偏好顺序对团队进行排名，从 1 最喜欢的团队到 M 最不喜欢的团队。现在的问题是找到一个匹配项，以便在每个团队最多可以有 K 名员工的限制下，员工最终会加入他们最喜欢的团队。
起初我以为，这是一个Assignment problem that could be solved using the Hungarian Algorithm。但后来我意识到，只有当每个工人都被分配到一个项目时，才能使用匈牙利算法。但在我的例子中，可以将几个工人分配到同一个团队。
现在我不确定这到底是什么问题。这是一个（多个） Knapsack problem or Bin packing problem 吗？我可以使用哪种算法来解决该问题？
稍微调整一下，就可以变成作业问题：
如果您将每个团队复制成 K 个容量为 1 的团队 - 那么您需要将每个工作人员分配给一个团队，并且每个团队只能分配给一个工作人员。
在分配问题中，代理和任务的数量不必相等。
有两种方法可以解决这个问题，哪种方法更有效取决于你有多少人和多少团队，K有多大。
更简单的方法（在@Alex L. 的回答中已经提到）是将每个团队分成 K 个团队，并将问题转换为常规加权二分匹配，可以用匈牙利算法。现在，匈牙利算法的复杂度是O(n^2 * m)。这里我们选择n作为人数，m作为团队的数量。我们将每个团队分成 k 后，最终的复杂度将是 O(n^2 * m * k).
另一种方法是将此问题视为最小成本最大流问题。您构建了一个图，源和汇是两个额外的节点，所有工作人员都直接连接到具有容量 1 和权重 0 的源，所有团队都连接到具有容量 [=15= 的汇] 和重量 0，以及连接到容量 1 和成本的团队的工作人员，具体取决于他们的偏好。 Min-cost max-flow 复杂度 O(n^3 * m)。现在，如果我们选择工人数量 n 和团队数量 m，我们会得到比匈牙利更糟糕的东西（因为大概是 k < n）。但是，如果我们将 n 设为团队数量，将 m 设为工人数量，我们可能会得到比匈牙利语更好的东西，如果工人数量很大，团队数量很少，并且k 也很大。
所以这完全取决于您的限制。如果 m 明显小于 k 和 n，你最好使用最小成本最大流，否则只需将团队分成 k 并使用香草匈牙利算法。
这是stable marriage problem。基本情况允许 1-1 匹配，但它可以很容易地概括为允许 1-K 匹配。在 1-K 匹配的情况下，团队不需要都具有相同的大小。团队也可能对某些特定的工人有优先于其他工人的偏好，或者可能对所有工人的偏好都是一样的。
如果团队没有偏好，这相当于首先将所有工人分配到他们最喜欢的团队。然后，如果有任何团队被超额订阅，则将额外的工作人员溢出到他们的第二偏好。重复直到分配完所有工作人员。
我们有 N 名工人，他们应该被分配到 M 个团队之一。每个团队最多可以有 K 名工人。每个工作人员按偏好顺序对团队进行排名，从 1 最喜欢的团队到 M 最不喜欢的团队。现在的问题是找到一个匹配项，以便在每个团队最多可以有 K 名员工的限制下，员工最终会加入他们最喜欢的团队。
起初我以为，这是一个Assignment problem that could be solved using the Hungarian Algorithm。但后来我意识到，只有当每个工人都被分配到一个项目时，才能使用匈牙利算法。但在我的例子中，可以将几个工人分配到同一个团队。
现在我不确定这到底是什么问题。这是一个（多个） Knapsack problem or Bin packing problem 吗？我可以使用哪种算法来解决该问题？
稍微调整一下，就可以变成作业问题：
如果您将每个团队复制成 K 个容量为 1 的团队 - 那么您需要将每个工作人员分配给一个团队，并且每个团队只能分配给一个工作人员。
在分配问题中，代理和任务的数量不必相等。
有两种方法可以解决这个问题，哪种方法更有效取决于你有多少人和多少团队，K有多大。
更简单的方法（在@Alex L. 的回答中已经提到）是将每个团队分成 K 个团队，并将问题转换为常规加权二分匹配，可以用匈牙利算法。现在，匈牙利算法的复杂度是O(n^2 * m)。这里我们选择n作为人数，m作为团队的数量。我们将每个团队分成 k 后，最终的复杂度将是 O(n^2 * m * k).
另一种方法是将此问题视为最小成本最大流问题。您构建了一个图，源和汇是两个额外的节点，所有工作人员都直接连接到具有容量 1 和权重 0 的源，所有团队都连接到具有容量 [=15= 的汇] 和重量 0，以及连接到容量 1 和成本的团队的工作人员，具体取决于他们的偏好。 Min-cost max-flow 复杂度 O(n^3 * m)。现在，如果我们选择工人数量 n 和团队数量 m，我们会得到比匈牙利更糟糕的东西（因为大概是 k < n）。但是，如果我们将 n 设为团队数量，将 m 设为工人数量，我们可能会得到比匈牙利语更好的东西，如果工人数量很大，团队数量很少，并且k 也很大。
所以这完全取决于您的限制。如果 m 明显小于 k 和 n，你最好使用最小成本最大流，否则只需将团队分成 k 并使用香草匈牙利算法。
这是stable marriage problem。基本情况允许 1-1 匹配，但它可以很容易地概括为允许 1-K 匹配。在 1-K 匹配的情况下，团队不需要都具有相同的大小。团队也可能对某些特定的工人有优先于其他工人的偏好，或者可能对所有工人的偏好都是一样的。
如果团队没有偏好，这相当于首先将所有工人分配到他们最喜欢的团队。然后，如果有任何团队被超额订阅，则将额外的工作人员溢出到他们的第二偏好。重复直到分配完所有工作人员。