什么是比蛮力更好的算法来区分重叠类别中的项目？
我有一个任意的项目集（下面的点），以及以任意方式重叠的一些类别（下面的A-C）。测试的目的是确定是否有可能将每个项目分配到一个单个类别中，这些类别已经属于这个类别，因此每个类别至少包含一定数量的项目。什么是比蛮力更好的算法来区分重叠类别中的项目？
因此，例如，我们可能要求A，B和C每个都可以要求一个项目。如果我们在下面给出所有4个点，则表明这是可能的，这很简单：只需将所有项目粘贴到列表中，循环遍历类别，然后让每个类别都删除它可以访问的项目，并且只要每个项目类别能够删除一个项目，我们通过测试。
现在假设我们删除了蓝点和重复测试。很显然，我们可以将黄色分配给A，将红色分配给B，将绿色分配给C，然后再次分配。但是很难对这个解决方案进行编纂：如果我们遵循先前的方法（再次没有蓝点），那么假设A从删除绿点开始。现在，如果B删除了黄点，我们将不能通过测试（因为C不能删除红点），而如果B删除了点，C仍然可以变黄并通过。
人们可以通过强制性的方法来解决这个问题，方法是迭代每个可能的项目分配到类别，检查每个迭代是否满足条件，但这不会很好地扩展到任意数量的项目和类别，并且我有一种感觉，有一种更聪明或更有效的方式。
我不知道这个问题的名称，这使得很难研究。它有最佳解决方案吗？如果是这样，我可以期待解决方案有多复杂？
让D表示您的点的集合，C表示一组类别。
可以构建二分图G（d ∪ C，E），其中，d ∪ C是一组顶点，E是一组d和C.
之间的边缘的（d，c）是E当且仅当点d属于类别c。
然后您有兴趣在此图中找到maximal bipartite matching。
因为图形是二分，其可以通过公知的Hopcroft–Karp algorithm
如果所计算的最大匹配的基数等于C大小解决，则有可能对每个类别匹配到一个不同的点和这个匹配描述这个分配。
您指出这是一个分配问题是正确的，因此可以使用图论经典算法来解决。
如下您可以转换您的问题：
一侧的节点代表的类别，而在另一侧的节点代表的项目。你想找到一个maximal match。这个问题可以简化为在bi-partite graph中找到maximal flow。
Fold-Fulkerson可用于在O（ES）中的二分图中找到最大匹配，其中E是边的数量，S是网络中的最大流量。
我还没有完全想到这一点，但感觉这应该是可以用动态编程方法解决的，因此从memoization中获益匪浅。 –
我觉得很难理解问题的形式性质。你的意思是“每个项目被分配到一个单一的类别*属于它的一个*，这样每个类别的结尾至少有*至少给定*数量的项目”？ –
@GiulioFranco，正好，编辑 – Shep