我有 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。
我相信我的方法无法产生最佳答案。
有人有更好的主意吗？
这是众所周知的集合覆盖问题。它是NP 难的——事实上，它的决策版本是典型的 NP 完全问题之一，并且是Karp 1972 年论文中包含的 21 个问题之一——因此没有已知的有效算法可以解决它。
您在问题中描述的算法被称为“贪婪算法”并且（除非您的问题有一些您没有告诉我们的特殊功能）它本质上是最知名的方法。它找到不超过 O(log |N|) 乘以最小的此类集合大小的集合。
听起来像是典型的回溯任务。
是的，如果你想快速得到一个好的答案，你的算法听起来很合理。如果您想组合尽可能少的样本，您最好尝试所有组合。
根据问题的确切结构，还有另一种通常效果很好的技术（并且实际上给出了最佳结果）：
让x[j]是一个布尔变量，表示选择是否在结果中包含第 j 个二进制序列。零抑制二元决策图现在可以表示（可能简洁 - 取决于问题的特征）集合族，使得对应x[j]于集合中包含的变量的二元序列的 OR 全为 1。如果 ZDD 简洁，则找到最小的此类集合（从而最小化包含的序列数量）相对容易。详细信息可以在计算机编程艺术第 7.1.4 章（第 4A 卷）中找到。
它也很容易适应精确的覆盖，通过采用一组集合，使得每个位置都有一个 1。