Math Is Fun Forum

mathmagic

Member

Registered: 2009-03-26

Posts: 1

Divide set of numbers into 2 sets so diff of their sums is min.

Howdy,

I'm trying to solve this problem, but can't seem to make much progress.

Given a set of positive numbers, divide it into 2 sets (which differ in size by 1, at max) so that the difference of their sums is minimum.

So, for e.g., given the following set: [8, 4, 25, 17], the possible combinations are:

1. [8,4] & [25,17] - 30
2. [8,25] & [4,17] - 12
3. [8,17] & [4,25] - 4

Clearly, the answer is 3: [4, 25] & [8, 17].

Thanks.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divide set of numbers into 2 sets so diff of their sums is min.

Hi mathmagic;

   Just from looking at your example if I were programming this I would first sort the list. Then I would make the first list by taking out the largest and smallest elements of the original list. After taking out half the elements by pairing them in this way I would form the second set using the rest of the elements in the original list. Still pairing the largest with the smallest. This should have the effect of balancing the differences of the sums of the list. If this does not produce the best answer it should always provide something close to it. This would be my first try.

bobbym

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Divide set of numbers into 2 sets so diff of their sums is min.

Ah, I see.
So you'd put the 1st and 4th quartiles in one set, and the 2nd and 3rd quartiles in another one.

I'd say the best solution to this would be found with an iterative process.
Use a method like bobby's to get a reasonable first guess, then apply some other method to improve the guess until it can't be improved any more.

Random example:

{2,9,3,14,7,12,5,24}

So then the first guess would be:

{2,3,14,24} = 43
{5,7,9,12} = 33

From here, we can try searching for two numbers to swap which would bring the totals closer together. This is a less complex task than the original, and a computer could quickly find:

{2,3,9,24} = 38 = {5,7,12,14}

It might take more than one step, but if the computer keeps swapping elements like this, in most cases it'll settle on a pretty good answer.

---

Why did the vector cross the road?
It wanted to be normal.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Divide set of numbers into 2 sets so diff of their sums is min.

Hi mathsyperson,

  The method I suggested would yield a good solution but not necessarily the optimal one. He should use your method to refine that solution, whether both of our ideas would yield the optimal solution in every case, I can't say.

   Looking at mathsypersons improvement, it might be wiser to alternately form the two lists biggest element and smallest in the first list. Then next biggest and next smallest in the second list and to alternate like this until the original list is exhausted.

bobbym

Last edited by bobbym (2009-04-17 00:17:44)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.