arrays - 如何交换两个数组的成员，使两个数组元素之和的差最小？

Question

给定两个无序数组 array1和 array2 , 长度均为 LEN .对于任何 i (0<=i<LEN) , 我可以交换 array1[i] 的值和 array2[i] .现在，我必须以某种方式交换它们，以便 array1 的元素总和之间的差异和 array2是最小的。

例如:

array1=[1, 3, 5]
array2=[2, 4, 9]

现在，如果我交换两个数组的第三个成员(5 和 9)，差值变为 (1+3+9)-(2+4+5)=2。

我找到了一个使用递归的解决方案。在我的解决方案中，我检查了所有有效组合以及差异最小的地方，这就是我的答案。但这里的运行时复杂度是 O(2^LEN) .我怎样才能更有效地做到这一点？

附言数组索引从 0 开始。

Answer 1

考虑第三个数组，其中 ith<​​ 条目是 array1 和 array2 中 ith<​​ 值的绝对差值>。为新数组中的这些差异分配符号等同于决定是否要交换原始数组中的值。您现在正在尝试解决最小化第三个数组中的(可能是符号交换的)值之和的问题。这是 Partition Problem 的优化版本.