1

Given is a set of elements. You have to divide them into groups of two, such that the difference between the sum of elements of an individual group is minimum.

example:

5
4 6 7 2 1

two groups are: {4,6} and {7,2,1}.

My approach: I have come across only the brute force solution of this problem, i.e. generate all the subsets (2^n) of the set using bit shifting technique.

I am looking for a better solution.

p0lAris
  • 4,750
  • 8
  • 45
  • 80
akash
  • 1,801
  • 7
  • 24
  • 42
  • 2
    possible duplicate of [divide an array into two sets with minimal difference](http://stackoverflow.com/questions/6597180/divide-an-array-into-two-sets-with-minimal-difference) – NPE Mar 05 '13 at 07:24
  • @H2CO3 this will not work I can give you a counter example: `{1,2,2,2,7}` – Ivaylo Strandjev Mar 05 '13 at 07:33
  • H2CO3, please post your answers as answers, not comments. – Emil Vikström Mar 05 '13 at 07:41
  • @IvayloStrandjev Proof please, I don't see what's wrong with that particular case. –  Mar 05 '13 at 07:42
  • @H2CO3 you will put 1 and 7 in the same group as being the minimal and maximal elements, while the best solution is in fact `{1,2,2,2}` and `{7}` having difference of 1 – Ivaylo Strandjev Mar 05 '13 at 07:43
  • @H2CO3 may we discuss this in [chat](http://chat.stackoverflow.com/rooms/25583/divide-the-set-into-group-of-two) – Ivaylo Strandjev Mar 05 '13 at 07:53
  • This is a *knapsack problem*, which is NP and has a pseudo polynomial solution based on DP. This problem must be a duplicate of something here. – phoeagon Mar 05 '13 at 15:02

1 Answers1

2

Instead of giving you the solution I will give you two tips:

  1. Calculate the sum of all elements and instead of solving the original problem. Denote this S. Solve a problem stated as follows - find a subset of the given numbers with sum no more than the S/2. The remaining numbers will form the other subset.

  2. The problem I describe above is very simplified knapsack problem with equal costs of all elements. Again it can be solved using dynamic programming(but in this case it will be way simpler than the one used for the classical knapsack problem)

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176