Group the numbers C++

Question

Here's the problem:

You have N (N represents the number of numbers that you have) numbers. Divide them in 2 groups in such way that the difference between sums of the numbers in the groups is minimal.

Examples:

5 // N

1, 9, 5, 3, 8 // The numbers

The difference is 0 if we put 1, 9 and 3 in Group A and 5 and 8 in Group B.

I think first I should calculate the sum of all numbers and divide it by 2. Then to check ever possible combination of numbers, whose sum is not higher than half of the sum of all numbers. After I do this I will choose the biggest number and print out the groups.

I have problem with going through all combinations, especialy when N is big numbers. How can I run through all combinations?

---

Also i think a little bit differently, I will group the numbers in descending order and i'll put the biggest number in Group A and lowest in Group B. Then I do the other way around. This works with some of the numbers, but sometimes it doesn't show the optimal grouping. For example:

If I use the previous example. Arrange the number in descending order.

9, 8, 5, 3, 1.

Put the biggest in Group A and lowest in Group B.

Group A: 9
Group B: 1

Other way around.

Group A: 9, 3
Group B: 1, 8

And so on. If in the end i have only one number I'll put it in the group with lower sum. So I finally will get:

Group A: 9, 3
Group B: 1, 8, 5

This isn't the optimal grouping because the difference is 2, but with grouping in different way the difference can be 0, as I showed.

How can I get optimal grouping?

CODE:

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int convertToBinary(int number) {
    int remainder;
    int binNumber = 0;
    int i = 1;
    while(number!=0)
    {
        remainder=number%2;
        binNumber=binNumber + (i*remainder);
        number=number/2;
        i=i*10;
    }
    return binNumber;
}
int main()
{
    int number, combinations, sum = 0;
    double average;
    cin >> number;
    int numbers[number];
    for(int i = 0; i<number; i++)
    {
        cin >> numbers[i];
        sum += numbers[i];
    }
    if(sum%2 == 0)
    {
        average = sum/2;
    }
    else
    {
        average = sum/2 + 0.5;
    }
    combinations = pow(2,number-1);
    double closest = average;
    for(int i = 0; i<=combinations;i++)
    {
        int rem;
        int temp_sum = 0;
        int state = convertToBinary(i);
        for(int j = 0; state!=0; j++)
        {
            int rem =state%10;
            state = state/10;
            if(rem == 1)
            {
                temp_sum = temp_sum + numbers[j];
            }
        }
        if(abs(average-temp_sum)<closest)
        {
            closest = abs(average-temp_sum);
            if(closest == 0)
            {
                break;
            }
        }
    }
    cout << closest*2;
    return 0;
}

Answer 1

Although this, as others have commented, is an NP-Complete problem, you have provided two fairly helpful bounds: you only want to split the group of numbers into two groups and you want to get the sums of the two groups as close as possible.

Your suggestion of working out the total sum of the numbers and dividing it by two is the right starting point - this means you know what the ideal sum of each group is. I also suspect that your best bet is to start by putting the largest number into, say, group A. (it has to go into one group, and it's the worst one to place later, so why not put it in there?)

This is when we get into heuristics which you cycle through until the groups are done:

N: Size of list of numbers.
t: sum of numbers divided by two (t is for target)

1. Is there a non-placed number which gets either group to within 0.5 of t? If so, put it in that group, put the remaining numbers in the other group and you're done.
2. If not, place the biggest remaining number in the group with the current lowest sum
3. go back to 1.

There will doubtless be cases that fail, but as a rough approach this should get close fairly often. To actually code the above, you will want to put the numbers in an ordered list so it is easy to work through them from largest to smallest. (Step 1 can then also be streamlined by checking (against both "groups so far") from largest remaining down until the "group so far" added to the number being checked are more then 1.0 below t - after that the condition cannot be met.)

Do let me know if this works!