在重叠的类别中，有什么比蛮力分离物品更好的算法？

Question

我有一组任意的项目（下面的点），一些数量的类别以任意的方式重叠（下面的A-C）。测试的目的是确定是否有可能将每一个项目分配到一个单独的类别中，在它已经属于的类别中，这样每个类别结束时至少有一定数量的项目。

例如，我们可能要求A、B和C可以各自要求一个项目。如果我们给出了下面所有的4个点，那么证明这是可能的就很容易了：只需将所有的项目贴在一个列表中，循环遍历类别，并让每个类别移除一个它也可以访问的项目，只要每个类别能够移除一个项目，我们就通过了测试。

现在假设我们移除蓝点并重复测试。很明显，我们可以把黄色分配给A，红色分配给B，绿色分配给C，我们再次通过。但是很难对这个解决方案进行编码：如果我们遵循前面的方法（同样没有蓝点），那么假设A从删除绿点开始。现在，如果B移除黄点，我们将不通过测试（因为C不能移除红点），而如果B移除红点，C仍然可以接受黄点并通过。

一个人可以通过对每一个可能的项到类别的分配进行迭代来解决这个问题，检查每一次迭代是否满足条件，但这不能很好地扩展到任意数量的项和类别，我觉得有一种更聪明或更有效的方法。

我不知道这个问题叫什么名字，所以很难研究。它有最优解吗？如果是这样，我能期望解决方案有什么样的复杂性？

Answer 1

你指出这是一个分配问题是对的，因此，它可以用图论的经典算法来解决。

您可以将您的问题解释为：

一侧的节点表示类别，另一侧的节点表示项目。你想找到一个最大匹配。这个问题可以归结为在二部图中求最大流。