Hello I have been thinking on a problem and I really don't know the algorithm . I need your help .
we have N numbers . we should choose some of them and calculate the difference between the sum of these numbers and the remaining numbers .
we call this difference HBN. The task is to find the smallest HBN between these numbers .
Given N and the N numbers please calculate the smallest difference between a groups of numbers and the remaining numbers .
Example 1 :
Input :
3
1 1 2
Output :
0
Example 2 :
Input :
3
1 5 1
Output :
3
Example 3 :
Input :
4
1 4 3 2
Output :
0
Note : HBN = |sum of remaining numbers — sum of picked numbers|
In the first example we can choose first and second number then the sum would be 2 and the HBN = |2-2| = 0
In the second example the minimum HBN happens when we choose the first and third number as a group and the remaining number is 5 . so HBN=|5-(1+1)|=|5-2|=3
In the third example the minimum HBN happens when we choose 1 and 4 as a group and the remaining numbers will be 3 and 2 . In this case HBN = |(1+4)-(2+3)|=|5-5|=0
note : the reason I have called this Hellium Balance is that the main problem is about how to balance some ballons filled with helliums such that the degree they turn is the minimum . in the first example the ballons turn 0 degrees .
Could you give some constraints on N? It is very important to know the largest value of N.
However I believe the problem is NP-Complete since it is very much like the Partition Problem.
However a O( 2^(N/2)*N ) solution exists as far as I know :
Partition the set of numbers in two groups, each with N/2 numbers. Then make all possible sums in each group. So we have 2 lists with 2^(N/2) numbers. Now note that each sum you can make from all numbers is simply a sum of two numbers, one from the first list and one from the second.
Now suppose that we sort those two lists and pick a number from the first list. Then what is the optimal number to pick from the second? Well it is optimal to pick "the largest number such that when the two numbers are summed their sum is less than or equal to the half of the sum of all numbers". This easily follows from the fact that the set we pick can always have sum that is less than or equal to the half of the sum of all numbers (if we assume the optimal solution doesn't pick such set, then we can take the numbers that weren't picked in the optimal solution and get such set with the same HBN).
Knowing that our algorithm works as follows:
Step 1 takes O( 2^(N/2)*2 ). Step 2 takes O( 2^(N/2)*log( 2^(N/2) )*2 ) = O( 2^(N/2)*(N/2)*2 ) = O( 2^(N/2)*N ) and Step 3 takes the same time as Step 2.
In the end if we simplify the complexity using big-O notation we get O( 2^(N/2)*N ).
Feel free to ask me if you couldn't understand something.
P.S. I believe that's a famous technique called Meet in the middle.
P.S.S. As mentioned below there is a way faster DP solution for not-so-large numbers, however the solution I described is if the numbers are arbitrary and its complexity does not depend on the numbers themselves.
if N * SumOfAllNumbers not so big, this broblem can be solved using DP.
bool dp[][]
dp[i][j] mean "can we get sum J using only some of first I numbers."
initialy: dp[0][0] = true; reccurence: we can take i + 1 number, dp[i + 1][j + a[i + 1]] = true;
and if we don't take i + 1 number then dp[i + 1][j] = true;
in the end u need to find number J such as dp[N][J] == true and abs(AllSum — J) is minimal.
note that sum can be negative.
Sry for my bad eng.