算法:找到包含整个域的最少集合数

Question

给定几个集合和一个数字n:

Here assume n is 5:
a - (0,1,2)
b - (0,1,2,3)
c - (1,3,4,5)
d - (0,1,2,4)
e - (2,3,4,5)
f - (3,5)

现在，如果我们只取 b 和 c，我们将得到从 0 到 5 的整个范围。

我正在考虑一种贪婪的方法，但它似乎不适合这里。

Answer 1

这是 set cover problem并且因此是 NP 完全的，这意味着您必须考虑所有可能的解决方案并选择最小的解决方案。