algorithm - 数组中给出与整个数组相同或值的最小元素数

Question

给定一个包含 n 个元素的数组。问题是从数组中找到最小数量的元素，这将导致与原始数组相同的 OR。

例如 arr[] = {1,2,3,4,6}。或数组中所有值的结果为 7。如果我们只考虑元素 6,1 和 OR，我们得到 7。所以答案是2。

我的方法是构造一棵由 0 和 1 组成的二叉树，0 为左 child ，1 为右 child 。

获取最终答案(即 7)遍历树并找到最接近的数字，该数字几乎涵盖了 7 的所有位。在第一步之后有点被击中。

任何人都可以提示如何进行下一次迭代。

Answer 1

这是 Set Cover problem ，这是 NP 难的。 OR 数组中的 1 位是被覆盖的集合和数组映射子集中的数字，即每个数字代表其二进制表示中设置的子集。

贪婪算法产生 log(N) 近似率。证明:https://www.cs.cmu.edu/~avrim/451f12/lectures/lect1106.pdf