假设C指的是一组容器{c1,c2,c3....cn}，其中每个容器都包含一组有限的整数{i1,i2,i3...im}。此外，假设整数可能存在于多个容器中。给定一组有限的整数S {s1,s2,s3...sz}，找出C其中包含所有整数的最小子集的大小S。
请注意，可能有数千个容器，每个容器都有数百个整数。因此，蛮力解决这个问题的速度很慢。
我尝试使用贪心算法来解决这个问题。也就是每次选择集合中整数个数最多的容器S，但都失败了！
任何人都可以为这个问题提出一个快速算法吗？
这是众所周知的集合覆盖问题。它是NP 难的——事实上，它的决策版本是典型的 NP 完全问题之一，并且是Karp 1972 年论文中包含的 21 个问题之一——因此没有已知的有效算法。除非你能确定问题的一些特殊的额外结构，否则你将不得不对一个近似结果感到满意：即 C 的一个子集，它的并集包含 S，但不一定是 C 的最小子集。
贪心算法可能是你最好的选择：它找到的集合的大小不超过 O(log |C|) 乘以最小的此类集合的大小。
你说你无法让贪心算法工作。我认为这可能是因为您未能正确实施它。你这样描述你的算法：
每次我选择集合 S 中整数个数最多的容器
但是通常的贪心算法的规则是在每个阶段选择集合 S 中整数个数最多的容器，这些整数目前不在任何选择的容器中。