我有一个问题，如下所述。你有什么好的解决方案，或者这个问题只是任何“经典”或“已解决”问题的另一种形式？
问题是 ：
有一些数字组，例如
一（1 8 9）
乙(1 4 5)
C(2 4 6)
D(3 4 7)
E(2 10 11)
F(3 12 13)
有“AF”六组。我们有数字“1,2,3,4,5,6,7,8,9,10,11,12,13”。现在找到满足每个组的最小数量的数字集合必须至少在这个集合中有一个数字。例如，我们可以找到集合“1 4 2 13 12”，A 有“1”，B 有“1,4”，C 有“2,4”，D 有“4”，E 有“2”， F 有 "12,13" 。
但是集合“1 2 4”并不是我们发现的，F在集合中没有任何数字。
最好的集合是“1,2,3”，每个组在集合中都有一个数字，集合的大小是最优的。它只有三个数字。这就是我们想要的。如果有很多最好的集合，找到任何一个都可以。谢谢。
这个问题是 NP-hard 通过从NP-hard 顶点覆盖问题减少而来的（给定一个图，你能找到一组 k 节点，使得图中的每个顶点都与某个选定的节点相邻吗？）
减少如下。以您喜欢的任何顺序对图表 1、2、3、...、n 中的所有节点进行编号。然后，对于图中的每条边，构建仅包含两个数字的集合 - 边的端点。如果原始图中有一个 k 节点顶点覆盖，那么您可以选择一组 k 个数字（即顶点覆盖中的节点），这样您就可以从每个集合中选择一个数字。这可以在多项式时间内计算。
要了解减少工作的原因，请注意，如果有一组大小为 k，您可以选择使得构造中的每个集合至少选择一个元素，然后对应于这些数字的顶点形成 k 元素顶点覆盖原图。
这种减少可以在多项式时间内完成，因此我们从 NP-hard vertex-cover 问题到您的问题进行了多项式时间减少。因此，这个问题是 NP 难的。因此，除非P = NP ，否则此问题没有多项式时间算法。
希望这可以帮助！
这相当于集覆盖问题。在这种情况下，您的每个集合 A、B、...、F 都是集合覆盖问题的元素，并且每个数字 1、2、...、13 都是集合。例如，在这个映射中，1 变为 {A, B}，而 11 变为集合 {E}。
套装封面是 NP-hard。链接的维基百科页面上的整数线性规划公式可能与您获得的精确解决方案一样好；贪心算法对于大问题有一个不错的近似值。