如何选择无重叠位的bitset得到最多1 求多项式时间解法是否存在

问题描述 #

给定N个包含M位的bitset，从中选择K个bitset，保证不存在多个bitset在同一位置均为1的情况，求可得到的1的最大数量是多少？

复杂度结论 #

该问题属于NP难问题，不存在普适的多项式时间复杂度最优解法，除非P=NP。
我们可以将经典NP难问题带基数约束的不相交子集最大化问题直接规约到该问题：

• 每个bitset对应一个待选子集，bitset中1的位置对应子集包含的元素，bitset中1的数量对应子集的权重
• 要求选K个互不相交的子集最大化总权重，和原问题完全等价，因此不存在可覆盖所有规模场景的多项式时间最优解法。

可行求解方案 #

小规模场景最优解法 #

如果参数规模较小，可以用状态压缩动态规划得到全局最优解：

• 适用场景：M ≤ 20
• 状态定义：dp[mask][k]表示选择k个bitset、已占用的位置掩码为mask时，能得到的最大1的数量
• 转移逻辑：遍历每个bitset，若该bitset的掩码和当前mask无重叠（即mask & bitset_mask == 0），则可以将该bitset加入选择，更新对应的状态值
• 最终结果：取所有k ≤ K的状态中的最大值即可

如果K或N的规模较小，也可以用回溯+剪枝的方法求解：优先遍历1的数量更多的bitset，提前剪掉不可能超过当前最优解的分支，提升搜索效率。

大规模场景近似解法 #

如果参数规模较大无法做全局搜索，可以用多项式时间的贪心算法得到近似解：

• 每次优先选择「1的数量/占用位置数」比值最高、且和已选bitset无冲突的bitset，直到选满K个或者没有符合要求的bitset为止
• 该方法可以在O(NKM)的时间复杂度内得到近似结果，但无法保证得到全局最优解

示例验证 #

输入：

N = 5, M = 6
001100
011010
100100
111001
001010

最优解为组合011010和100100，两个bitset没有重叠的1位，总1的数量为3+2=5，符合预期。 #

内容的提问来源于stack exchange，提问作者Y.T.