algorithm - 从许多二进制序列中选择一些，使得 "or"它们加在一起的结果是 1111111111....111

Question

我有 N 个长度为 L 的二进制序列，其中 N 和 L 可能非常大，而且这些序列可能非常稀疏，比如 0 比 1 多得多。

我想从中选出M个序列，即b_1、b_2、b_3...，这样

b_1 | b_2 | b_3 ... | b_M = 1111...11 (L 1s)

有算法实现吗？

我的想法是:

STEP1:对于从1到L的位置，统计该位置为1的序列总数。将其命名为“拥有号码”

STEP2:考虑拥有数最小的位置，从该位置的拥有序列中选择1个数最多的序列。

STEP3:忽略选择的序列，更新拥有号并返回STEP2。

我认为我的方法无法生成最佳答案。

有没有人有更好的主意？

Answer 1

这是众所周知的set cover problem .是NP-hard — 事实上，它的决策版本是典型的 NP 完全问题之一，并且是 Karp's 1972 paper 中包含的 21 个问题之一。 — 因此，目前还没有解决该问题的有效算法。

您在问题中描述的算法被称为“greedy algorithm”并且(除非您的问题有一些您没有告诉我们的特殊功能)它本质上是最知名的方法。它找到一个不超过 O(log |N|) 倍于最小此类集合大小的集合。