我有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)
有算法可以实现吗？
我的想法是：
步骤1：对于从1到L的位置，计算该位置有1的序列总数。将其命名为"拥有编号"
步骤2：考虑拥有最小数量的位置，并从该位置的拥有序列中选择拥有最大数量1s的序列。
步骤3：忽略所选序列，更新所属号码并返回步骤2。
我相信我的方法不能产生最好的答案。
有人有更好的主意吗？
这是众所周知的集覆盖问题。它是NP难的——事实上，它的决策版本是典型的NP完全问题之一，也是Karp 1972年论文中包含的21个问题之一——因此还没有有效的算法来解决它
你在问题中描述的算法被称为"贪婪算法"，（除非你的问题有一些你没有告诉我们的特殊特征）它本质上是最著名的方法。它查找一个集合集合，该集合的大小不超过最小集合大小的O（log|N|）倍。
听起来像是一个典型的回溯任务。
是的，如果你想快速得到一个好的答案，你的算法听起来很合理。如果你想拥有尽可能少的样本组合，你最好尝试所有的组合。
根据问题的确切结构，还有一种其他技术通常效果良好（实际上会给出最佳结果）：
设x[j]是一个布尔变量，表示是否在结果中包括第j个二进制序列的选择。零抑制二进制决策图现在可以表示（可能简洁地-取决于问题的特征）集合族，使得与包含在集合中的变量x[j]相对应的二进制序列的OR都是1。如果ZDD简洁，那么找到最小的这样的集合（从而最小化包含的序列数量）相对容易。有关详细信息，请参阅《计算机编程艺术》第7.1.4章（第4A卷）。
也很容易适应精确的封面，方法是采用集合族，使每个位置都有一个1。