给定一个包含 n 个元素的数组。问题是从数组中找到最小数量的元素,这将导致与原始数组相同的 OR。
例如 arr[] = {1,2,3,4,6}
。或数组中所有值的结果为 7。
如果我们只考虑元素 6,1 和 OR,我们得到 7。所以答案是2。
我的方法是构造一棵由 0 和 1 组成的二叉树,0 为左 child ,1 为右 child 。
获取最终答案(即 7)遍历树并找到最接近的数字,该数字几乎涵盖了 7 的所有位。在第一步之后有点被击中。
任何人都可以提示如何进行下一次迭代。
最佳答案
这是 Set Cover problem ,这是 NP 难的。 OR 数组中的 1
位是被覆盖的集合和数组映射子集中的数字,即每个数字代表其二进制表示中设置的子集。
贪婪算法产生 log(N) 近似率。证明:https://www.cs.cmu.edu/~avrim/451f12/lectures/lect1106.pdf
关于algorithm - 数组中给出与整个数组相同或值的最小元素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50713179/