algorithm - 分配整数对

Question

如何解决这个问题：
给定 N 对整数。对于每一对整数，我们必须将一个整数分配给 A，另一个分配给 B，使得分配给 A 的整数之和与分配给 B 的整数之和之间的差异最小。
我想不出比 O(2^N) 更好的东西了。
我想到了贪婪，但它并不总是给出最佳结果。

Answer 1

将问题转化为：

给定：一个非负整数序列（原始对之间的绝对差）
问题：将整数分成两组，以最小化每个子集元素之和的绝对差。

这是NP完全的平衡分区问题。这两个问题是等价的；也就是说，您可以将平衡分区问题转换为您的问题：为序列的每个元素 n _i关联整数对 (n _i , 0)。因此，你不会比 O(2 ^N ) 做得更好。

问题：为每个整数分配一个符号（加/减），以使序列和的绝对值最小。

我怀疑^*如果您首先按降序对序列进行排序，那么贪心算法将给出最佳结果。这将是一个 O(N log N) 算法。

( ^* ) 如果我错了，请发布一个反例。

Answer 2

让这些对为 (A_0,B_0),...,(A_n,B_n)。令 D_i = |A_i-B_i|。那么你的问题相当于为 D_i 选择符号以最小化总和，这相当于找到一个 D_i 的子集，其总和为总和的一半，相当于子集和，即 NP 完全。所以你不会比 2^n 做得更好。

除了：如果数字很小，您可以尝试动态编程方法：DP[i][n] 为真，前提是您可以使用 D_0,..,D_i 选择一个与 n 相加的子集。您从 DP[0][0] 为真开始，然后如果 DP[i][n] 为真或 DP[i][nD[i+1]] 为真，则 DP[i+1][n] 为真真的。这个解决方案是 O(n*(最大可能的总和))