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 eachi
.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 arei_1,...,i_k
chosen toD_1
andj_1,...,j_m
chosen toD_2
(and each index is in i's or j's), such that:From the construction, it means:
and thus:
From this:
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: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.