arrays - 数组所有子集中的最大或值

Question

给定一个包含 n 个整数的数组。在给定数组的所有子集中找到具有最大或值的子集的最小长度。

如何解决这个问题？

Answer 1

最大 OR 只是所有项目的 OR，唯一真正的问题是找到与该值 OR 的最小子集。

这是 Set Cover 问题的搜索版本，既可以通过将其视为 Set Cover 搜索版本的实例来解决，也可以在以下方面编写 Set Cover 实例这个问题的术语，所以它是 NP 难的(不是 NP 完全的，因为它不是决策问题)。

您可以使用整数线性规划、SAT 求解(由于 SAT 未优化，因此需要多次查询)、动态规划以及毫无疑问的其他技术来解决这个问题。

---

例如，要使用 DP，我们可以执行如下操作，假设 WLOG^* 输入数组 (A) 的 OR 是 m 是 2 减 1 的幂。(* 因为任何始终为 0 的位位置都可以忽略并从问题中删除而不更改结果子集)

建立一个大小 S 的表，使得 S[i][x] 是 A[0..i 的最小子集的大小] 覆盖掩码 x。

S[0][0] = 0
for x in 1..m+1:
    S[0][x] = n+1
for i in 0..n:
    for x in 0..m+1:
        S[i+1][x] = min(S[i][x & ~A[i]] + 1, S[i][x])

最小覆盖层的大小在 S[n][m] 中找到，覆盖层本身可以用通常的“向后路径跟踪”方法重建。如果 min 的左操作数对应于包含项 i，如果 min 的右操作数对应于 不 包括项目 i，如果它不明确，那么任何一条路径都会导致同样好的解决方案。

与基于 SAT 或 ILP 的算法不同，此算法无法利用问题实例可能具有的任何有用结构。