我有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:考虑具有最小拥有数的位置,并从该位置的拥有序列中选择具有最大数量1的序列.
第3步:忽略所选序列,更新拥有号码并返回STEP2.
我相信我的方法无法产生最佳答案.
有没有人有更好的主意？
这是众所周知的套装问题.它是NP难的 - 实际上,它的决策版本是规范的NP完全问题之一,并且是Karp 1972年论文中包含的21个问题之一- 因此没有解决它的有效算法.
您在问题中描述的算法被称为" 贪婪算法 ",并且(除非您的问题具有一些您没有告诉我们的特殊功能),它本质上是最着名的方法.它找到的集合集合不超过最小此类集合的大小的O(log | N |)倍.