algorithm - 选择 k 个数最大化成对异或的和

Question

给定一个范围 [l, r] (其中 l < r )和一个数字 k (其中 k <= r - l )，我想选择一组 S的 k [l, r] 中的不同数字最大化成对异或的总和。例如，如果 [l, r] = [2, 10]和 k = 3我们选择S = {4, 5, 6} , 异或之和为 d(4, 5) + d(4, 6) + d(5, 6) = 1 + 1 + 2 = 4 .

到目前为止，这是我的想法:在 [l, r] 中, 对于每个位索引 i小于或等于 r 中最高设置位的索引, S ^ S 中的元素数量与 i第 bit 集等于 j * (k-j) , 其中j是 S 中元素的数量与 i第位设置。为了优化这一点，我们要选择 S这样，对于每一位 i , S包含 k/2带有 i 的元素第位设置。这对于 k = 2 来说很容易，但我坚持将其概括为 k > 2 .

Answer 1

乍一看，这个问题似乎没有代数解。我的意思是，这似乎是一个无法在多项式时间内解决的 NP-hard 问题(优化问题)。

几乎总是可以通过可行空间暴力破解。

凭直觉，我可以建议查看 Locality Sensitive Hashing .在 LSH 中，人们通常会尝试找到两组之间的相似之处。但在您的情况下，您可以在以下意义上滥用此算法。

• 域被分割为几个桶。
• 您在空间 [l,r] 中随机采样点。
• 高概率点(大汉明距离)被放置在桶中。
• 最后，您在最有可能的桶中使用蛮力。

最后，可以预期具有较大汉明距离的点应该在同一邻域内(这就是名称​​局部敏感散列的原因)。然而，这只是一个想法。