Здесь проблема:
У вас есть N (N - число номеров, которые у вас есть). Разделите их на 2 группы таким образом, чтобы разница между суммами чисел в группах была минимальной.
Примеры:
5 // N
1, 9, 5, 3, 8 // The numbers
Разница равна 0, если мы поместим 1, 9 и 3 в группу A и 5 и 8 в группу B.
Сначала я должен вычислить сумму всех чисел и разделить ее на 2. Затем проверить всю возможную комбинацию чисел, сумма которых не превышает половину суммы всех чисел. После этого я выберу самое большое число и распечатаю группы.
У меня проблема с просмотром всех комбинаций, особенно если N - большие числа. Как я могу запускать все комбинации?
Также я думаю немного по-другому, я буду группировать числа в порядке убывания, и я положу наибольшее число в группе А и самый низкий в группе B. Тогда я делаю наоборот. Это работает с некоторыми номерами, но иногда оно не показывает оптимальную группировку. Например:
Если я использую предыдущий пример. Расположите номер в порядке убывания.
9, 8, 5, 3, 1.
Поместите самые большие в группе А и самые низкие в группе В.
Group A: 9
Group B: 1
Другой способ.
Group A: 9, 3
Group B: 1, 8
И так далее. Если в конце у меня будет только одно число, я поставлю его в группу с более низкой суммой. Поэтому я, наконец, получу:
Group A: 9, 3
Group B: 1, 8, 5
Это не оптимальная группировка, потому что разница равна 2, но при группировке по-разному разница может быть 0, как я показал.
Как я могу получить оптимальную группировку?
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;
}
