optimization - 算法 - 找到两个数组之和之间的最小减法

Question

我现在正在找工作并做很多算法练习。这是我的问题:

给定两个数组:a 和 b 长度相同，题目是做 |sum(a)-sum(b)|最小，通过在 a 和 b 之间交换元素。

这是我的:

假设我们交换 a[i] 和 b[j]，设置 Delt = sum(a) - sum(b)，x = a[i]-b[j]
然后 Delt2 = sum(a)-a[i]+b[j] - (sum(b)-b[j]+a[i]) = Delt - 2*x，
那么变化 = |Delt| - |Delt2|，与 |Delt|^2 成正比 - |Delt2|^2 = 4*x*(Delt-x)，

基于上面的想法，我得到了以下代码:

Delt = sum(a) - sum(b);
done = false;
while(!done)
{
    done = true;
    for i = [0, n)
    { 
        for j = [0,n)
        {
            x = a[i]-b[j];
            change = x*(Delt-x);
            if(change >0)
            {
                 swap(a[i], b[j]);
                 Delt = Delt - 2*x;
                 done = false;
            }
        }
    }
}

但是，有人有更好的解决方案吗？如果你有，请告诉我，我会很感激你!

Answer 1

这个问题基本上是Partition Problem的优化问题具有相等部分的额外约束。我将证明添加此约束不会使问题变得更容易。

NP-Hardness证明:
假设有一个算法 A在多项式时间内解决这个问题，我们可以解决Partition-Problem在多项式时间内。

Partition(S):
for i in range(|S|):
   S += {0}
   result <- A(S\2,S\2) //arbitrary split S into 2 parts
   if result is a partition: //simple to check, since partition is NP.
     return true.
return false //no partition

正确性:
如果有一个分区表示为 (S1,S2) [假设 S2 有更多元素]，则在迭代 |S2|-|S1| [IE。添加 |S2|-|S1| 时零]。 A 的输入将包含足够的零，因此我们可以返回两个等长数组:S2,S1+{0,0,...,0}，这将是 S 的一个分区，并且算法将产生真。
如果算法结果为真，则迭代 k ，我们有两个数组:S2，S1，具有相同数量的元素和相等的值。通过删除 k从数组中取零，我们得到原始 S 的一个分区，所以 S 有一个分区。

多项式:
假设 A需要 P(n)时间，我们产生的算法将花费 n*P(n)时间，这也是多项式。

结论:
如果这个问题可以在多项式时间内解决，那么分区问题也是如此，因此 P=NP。基于此:这个问题是 NP-Hard。

因为这个问题是 NP-Hard，对于精确的解决方案，您可能需要指数算法。其中之一很简单 backtracking [我把它作为练习留给读者来实现一个回溯解决方案]

编辑 :正如@jpalecek 所提到的:通过简单地创建一个减少: S->S+(0,0,...,0) [k × 0]，可以直接通过归约证明NP-Hardness。多项式是微不足道的，正确性与上述分区的正确性证明非常相似:[如果有分区，则可以添加“平衡”零；另一个方向只是修剪那些零]