algorithm - 最小元素数 使用 xor 生成所有其他元素

Question

我有 n 个整数 a_1, ..., a_n。我想从异或形成其他人的所有人中选择最小数量。

例如，考虑 [1,2,3]，1^3=2 所以你不需要 2大批。所以你可以删除它。以 [1,3] 结束。所以元素的最小数量是 2 并且它们可以通过对其中的任意 2 个进行异或来形成数组中的所有原始元素。贪婪的方法在这里行得通吗？还是 DP？

编辑:解释我的想法。我想到的一个贪婪的方法是因为如果 a^b=c 那么 a^c=b 和 b^c=a。首先，我删除所有重复项。然后我会首先在开头列出每个元素可以配对以形成数组中另一个元素的所有对。预处理需要 O(n^3)。然后我选择贡献最少的元素并将其删除，然后从其他每个元素中减去 1。我重复这个直到所有元素都有 <=2 对。我停下来。这也需要 O(n^3) 总共 O(n^3)。这种贪心的方法行得通吗？有DP的方法吗？

Answer 1

如果 n 以 50 为界，我认为回溯应该有效。

假设在某个步骤中我们已经选择了数字的 S 子集(应该产生所有其他数字)并且想要将一个新数字包含到该子集中。然后我们可以执行以下操作:

• 考虑所有剩余的数字 R 并在 S 中包含其他人无法产生的所有数字(在 S 和 R)
• 在 S 中包含一个来自 R
的随机(或某种意义上的“最佳”)数字
• 从 R 中删除更新后的 S 中的所有数字

您还应该跟踪当前的最佳解决方案并切断所有不允许获得更好结果的分支。