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

Question

我现在正在找工作，做很多算法练习。我的问题是：

给定两个数组:a和b，主题是通过在a和b之间交换元素，使-sum(B)\x最小。

这是我的想法：

假设我们交换ai和bj，设Delt = sum(a) - sum(b)，x= ai-bj

则Delt2 = sum(a)-ai+bj - (sum(b)-bj+ai) =Delt-2*x，

然后是变化=x，x=x= 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-硬度证明：

假设有一个算法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-sx-x-s1的迭代中，即当添加回s2收-s1-s1零时。A的输入将包含足够的零，因此我们可以返回两个等长数组: S2，S1+{0,0，...,0}，这将是对S的分区，该算法将得到真结果。

如果算法生成true和迭代k，那么我们有两个数组: S2、S1，它们具有相同的元素数和相同的值。通过从数组中移除k零，我们得到一个到原始S的分区，因此S有一个分区。

多项式：

假设A占用P(n)时间，我们提出的算法将花费n*P(n)时间，这也是多项式。

结论：

如果这个问题在多项式时间内是可解的，那么Partion-问题也是如此，因此也是P=NP问题.基于此:这个问题是NP难的。

因为这个问题是NP难的，要精确地解决这个问题，你可能需要一个指数算法。其中一个是简单的回溯，我把它留给读者来实现回溯解决方案。

编辑：正如@jpalecek所提到的:通过简单地创建一个约简：S->S+(0,0,...,0) k乘以0，就可以通过简化直接证明NP-硬度。多项式是琐碎的，正确性非常类似于上面分段的正确性证明:如果有一个分区，添加“平衡”零是可能的；另一个方向是简单地修剪那些零。

Answer 2

只是说说而已。通过所有这些交换，您基本上可以根据需要排列两个数组的内容。因此，值在哪个数组中处于起始位置并不重要。

在我脑子里做不到，但我很确定有一个建设性的解决办法。我认为如果你先对它们进行排序，然后按照某些规则处理它们。类似于If value > 0 and if sum(a)>sum(b) then insert to a else into b的东西