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

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

这个问题基本上是带有额外的等份约束的分区问题的优化问题。我将证明添加这个约束并不会让问题变得更容易。

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

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| 时 [即添加|S2|-|S1|时 零]。的输入A将包含足够的零，因此我们可以返回两个等长数组：S2,S1+{0,0,...,0}，这将是 的分区S，算法将产生 true。
如果算法产生 true 且迭代k，我们就有两个数组：S2,S1，具有相同的元素数量和相等的值。k通过从数组中删除零，我们得到了原始 S 的一个分区，因此 S 有一个分区。

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

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

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

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