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

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< /code>，算法将得出 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-还原硬度。多项式是微不足道的，正确性与上述分区的正确性证明非常相似：[如果存在分区，则可以添加“平衡”零；另一个方向只是修剪那些零]

Answer 2

只是一个评论。通过所有这些交换，您基本上可以根据需要排列两个数组的内容。因此，值在哪个数组中开始并不重要。

我无法在脑海中做到这一点，但我很确定有一个建设性的解决方案。我认为如果你先对它们进行排序，然后根据某种规则进行处理。类似的东西 If value > 0 并且如果 sum(a)>sum(b) 则插入 a else into b