This is the problem:
You have two arrays A and B, of equal length. You have to partition them into two groups P and Q such that: (1) Their difference is minimized. (2) If A[i] goes into one of P or Q, B[i] should go into another.
Here is a link to the actual problem: http://opc.iarcs.org.in/index.php/problems/EQGIFTS
This is my logic (to solve the actual problem):
if the input is : a b c d e f g, a list of values and the index of a,b,c,d,e,f is 0,1,2,3,4,5 respectively
if t is a index of a,b,c,d,e,f,g the program checks for t and i such that: the value at [t] > value at [t-i] , beginning with t = 5, and i = 1, and increasing the value of i by 1 and decreasing the value of t by 1.
as soon as it finds a match, it swaps the values of both the indices and sorts the values beginning from [t-1]. the resulting list of values is the output.
I don't know what is wrong with this algorithm, but it produces a wrong answer for all the test cases. I know it can be solved using dynamic programming, and that it is a variation of the partition problem. But i don't know how to change the partition algorithm to solve this problem.
Reduce the problem to partition problem:
Create a third array D[i] = B[i] - A[i] for each i.
Now the problem is a classic partition problem on the array D, and you can use its DP solution to have a pseudo-polynomial time solution.
Correctness Proof:
If there is a solution on D (sum(D_1) = sum(D_2)) - then there are i_1,...,i_k chosen to D_1 and j_1,...,j_m chosen to D_2 (and each index is in i's or j's), such that:
sum(D[i's]) = sum(D[j's])
From the construction, it means:
sum(B[i]-A[i]) = sum(B[j]-A[j]) (for each relevant i's,j's)
and thus:
sum(B[i's]) - sum(A[i's]) = sum (B[j's]) - sum(A[j's])
From this:
sum(B[i's]) + sum(A[j's]) = sum(B[j's]) + sum(A[i's])
which exactly what we wanted, since each "index" is assigned to both parts, one part gets a B and the other gets A.
The other direction is similar.
QED
Complexity of the problem:
The problem is still NP-Hard with the simple reduction:
Given an instance of Partition Problem (S=[a_1,a_2,...,a_n]), create the instance of this problem:
A=S, B=[0,...,0]
It is easy to see that the same solution that gives optimal solution to this problem will be the needed partition to the original partition problem, and thus the problem is NP-Hard.