算法 - 找到代表所有行的最小单元格子集

我有几个列表，您可以将它们视为整数行。 例如 ：

[1 3 5]
[3 7]
[3 5 7]
[1 5 9]
[3 9]
[1 7]
[5 9 11]

我希望找到这些行上表示的最小可能的整数集，以便：

• 每行至少有一个选定的整数，
• 如果存在基数关系，请选择总和最高的集合。

在我的示例中，我相信结果应该是 [5 7 9] （首选 [3 5 7] 或 [1 3 11] 或......许多可能性）。

第二部分很简单（选择最高和），但是基数中所有最小子集的生成似乎很困难。

你知道实现这一目标的好方法吗？

Edit

数据大小随着迭代缓慢增长，但我需要精确匹配。

最小基数版本是 NP 完全的。设置封面 http://en.wikipedia.org/wiki/Set_cover_problem可以简化为这样。要求其中的最大值只会使问题变得更加困难。

顺便说一句，谈论布尔可满足性的另一个答案是wrong！您需要减少此问题的布尔可满足性以显示 NP 完备性，而不是相反。

设置封面基本上是：

给出集合 S1, S2, ... Sn 的集合 X 的子集，找到其并集涵盖 S1 U S2 U ... U Sn 中的所有元素的最小子集合（就集合数量而言） 。

为了减少我们的问题，

设 S = S1 U S2 ... U Sn。 = {x1, x2, ..., xm}

令 C_i = { j 使得 xi 在 Sj 中 }

将 C_i 提供给我们的问题。

现在，如果我们的问题可以在多项式时间内解决，并且我们可以找到 C_i 元素的最小基数集，那么我们可以找到 Si 的集合覆盖，反之亦然。

这通常可以作为整数规划问题来解决（这也是 NP-Hard）。

对于近似解，这可以被视为线性规划问题（具有多项式时间算法），并且可以进行随机舍入以将小数值（LP 的解）转换为整数。

另外，不幸的是，事实证明，即使是接近一个常数因子，这也是 NP 困难的（事实上我相信它是 O(logn)）。