将项目分配到最小数量的组

Question

这是一个流行的CS模式，但我显然缺少一些关键字，因为我没有任何运气搜索它。

我有一组4个项目：[A，B，C，D]。

我有3组：1，2，3

组1可以接受A或B.

组2可以接受B或C.

组3可以接受C或d 。

以最小化使用组数的方式分配项目。 也就是说该解决方案将是： 第1组：[A，B]

组2：[]

组3：[C，d]

我将如何解决这个编程？我知道我以前见过这个，所以任何关键字或链接都指向正确的方向将非常感激。

Answer 1

这是设定的覆盖问题。这是NP很难的，因此找到真正的最小集合一般很难，并且需要指数时间。使用覆盖最多剩余元素的集合的贪婪算法可以给出很好的近似值。为了覆盖有限大小的集合，也可以在合理的时间内解决。详情请参阅http://en.m.wikipedia.org/wiki/Set_cover_problem

Answer 2

如果我们想象此问题作为一个图形的问题，其中所有的组和项目是图中的节点，并有边缘的组和项目之间进行连接，我们可以看到，这个问题是Vertex Cover

小的情况下

但是，如果项目数量很少（小于16），我们可以使用动态编程来轻松解决。