arrays - 通过补充位掩码确定最大和数组的算法

Question

我的同事提出的这个问题让我很困惑。我什至无法想出一个干净的蛮力解决方案。陈述问题:

给定一个包含非负整数的大小为 n 的数组，k = [10, 40, 1, 200, 5000, ..., n]，a大小为 n 的位掩码，即 mask = 1001....b_n 其中 |mask| = n. 和一个表示可以互补的连续位的整数 S = 3，找到产生最大总和数组的掩码配置。

补码大小 S 用于从位掩码中选取 S 连续位并用其补码替换它。

例如，如果 mask = 100001 和 S = 2 你可以

• 通过在 MSB 处应用掩码，将 mask 更改为 010001
• 您可以迭代地继续补充 mask 中的任何位，直到找到最大大小的数组。

这是我想出的:

1. 找到所有 2^n 位掩码配置，然后应用它们找到最大总和数组
2. 给定初始掩码配置，看看是否存在到步骤 1 中找到的最大总和数组配置的路径。

我的也是一个指数解。任何有效的方法都值得赞赏。

Answer 1

从琐碎的观察开始，您永远不会应用给定的位掩码 G ，它仅由 S 组成1 s，在你原来的面具的同一段上不止一次，M - 这是因为按位异或是可交换的和关联的，允许您随心所欲地重新排序，并且将位掩码异或给它自己给你所有 0秒。

给定一个位掩码 B长度S , 和一个积分索引 ind在 [0,n) , 让BestSum(ind, B)是可以在 [ind:n) 上获得的最佳总和输入数组的切片 k什么时候M'[ind, ind + S) = B , 其中M'是执行所有操作后掩码的最终状态。让我们写B = b.B' , 其中b是 MSB 并考虑 b 的两种可能性:

1. b = M[ind] : 在这种情况下，您将不会申请 G在 M[ind]因此 BestSum(ind, B) = b*k[ind] + max(BestSum(ind + 1, B'.0), BestSum(ind + 1, B'.1)) .
2. b != M[ind] : 在这种情况下，您将申请 G在 M[ind]因此 BestSum(ind, B) = b*k[ind] + max(BestSum(ind + 1, (~B').0), BestSum(ind + 1, (~B').1)) .

这与边界条件一起为您提供了运行时间为 O(n*2^S) 的 DP .最好的解决方案是 max over all BestSum(0, B) .

请注意，我们已将所有可达性问题都隐藏在“边界条件”之下。现在让我们解决这个问题——如果，对于给定的 ind和 B ，没有最终配置M'这样 M'[ind, ind + S) = B , 定义 BestSum(ind, B) = -inf .这将确保您需要回答不可达性的唯一情况确实是边界 - 即 ind = n - S . (n-S, B) 的唯一值可通过 (n-S, M[n-S:n)) 访问和 (n-S, M[n-S:n) ^ G) , 从而轻松处理边界。