Algorithm - find the minimal subtraction between sum of two arrays

I am hunting job now and doing many algorithm exercises. Here is my problem:

---

Given two arrays: a and b with same length, the subject is to make |sum(a)-sum(b)| minimal, by swapping elements between a and b.

---

Here is my though:

assume we swap a[i] and b[j], set Delt = sum(a) - sum(b), x = a[i]-b[j]

then Delt2 = sum(a)-a[i]+b[j] - (sum(b)-b[j]+a[i]) = Delt - 2*x,

then the change = |Delt| - |Delt2|, which is proportional to |Delt|^2 - |Delt2|^2 = 4*x*(Delt-x),

Based on the thought above I got the following code:

---

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;
            }
   开发者_C百科     }
    }
}

---

However, does anybody have a much better solution ? If you got, please tell me and I would be very grateful of you!

---

This problem is basically the optimization problem for Partition Problem with an extra constraint of equal parts. I'll prove that adding this constraint doesn't make the problem easier.

NP-Hardness proof:
Assume there was an algorithm A that solves this problem in polynomial time, we can solve the Partition-Problem in polynomial time.

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

Correctness:
If there is a partition denote as (S1,S2) [assume S2 has more elements], on iteration |S2|-|S1| [i.e. when adding |S2|-|S1| zeros]. The input to A will contatin enough zeros so we can return two equal length arrays: S2,S1+{0,0,...,0}, which will be a partition to S, and the algorithm will yield true.
If the algorithm yields true, and iteration k, we had two arrays: S2,S1, with same number of elements, and equal values. by removing k zeros from the arrays, we get a partition to the original S, so S had a partition.

Polynomial:
assume A takes P(n) time, the algorithm we produced will take n*P(n) time, which is also polynomial.

Conclusion:
If this problem is solveable in polynomial time, so does the Partion-Problem, and thus P=NP. based on this: this problem is NP-Hard.

Because this problem is NP-Hard, for an exact solution you will probably need an exponential algorith. One of those is simple backtracking [I leave it as an exercise to the reader to implement a backtracking solution]

EDIT: as mentioned by @jpalecek: by simply creating a reduction: S->S+(0,0,...,0) [k times 0], one can directly prove NP-Hardness by reduction. polynomial is trivial and correctness is very similar to the above partion's correctness proof: [if there is a partition, adding 'balancing' zeros is possible; the other direction is simply trimming those zeros]

---

Just a comment. Through all this swapping you can basically arrange the contents of both arrays as you like. So it is unimportant in which array the values are at start.

Can't do it in my head but I'm pretty sure there is a constructive solution. I think if you sort them first and then deal them according to some rule. Something along the lines If value > 0 and if sum(a)>sum(b) then insert to a else into b