Ответ 1
Используя ограничение только двух групп, проблема zour уже решена, если вы можете найти одну группу чисел, сумма которых точно равна половине общего числа. таким образом, я предлагаю вам попробовать найти эту группу и, очевидно, поместить остальную часть в другую группу.
Предположение о том, что наибольшее количество в первой группе является простым. Теперь все остальное сложнее.
Это просто в двоичной системе: считайте, что для каждого числа у вас бит. Бит beeing 1 сигнализирует, что число находится в группе A, в противном случае оно находится в группе B. Весь дистрибутив можно описать путем объединения этих битов. Это можно считать числом. SO, чтобы проверить все комбинации, которые вы должны пройти через все числа, и вычислить комбинацию.
код:
#include <iostream>
#include <memory>
using namespace std;
int partition(const std::unique_ptr<int[]>& numbers, int elements) {
int sum = 0;
for(int i=0; i<elements; ++i) {
sum += numbers[i];
}
double average = sum/2.0;
double closest = average+.5;
int beststate = 0;
for(int state=1; state< 1<<(elements-1);++state) {
int tempsum = 0;
for(int i=0; i<elements; ++i) {
if( state&(1<<i) ) {
tempsum += numbers[i];
}
}
double delta=abs(tempsum-average);
if(delta < 1) { //if delta is .5 it won't get better i.e. (3,5) (9) => average =8.5
cout << state;
return state;
}
if(delta<closest) {
closest = delta;
beststate = state;
}
}
return beststate;
}
void printPartition(int state, const std::unique_ptr<int[]>& numbers, int elements) {
cout << "(";
for(int i=0; i<elements; ++i) {
if(state&(1<<i)) {
cout << numbers[i]<< ",";
}
}
cout << ")" << endl;
}
int main()
{
int elements;
cout << "number of elements:";
cin >> elements;
std::unique_ptr<int[]> numbers(new int[elements]);
for(int i = 0; i<elements; i++)
{
cin >> numbers[i];
}
int groupA = partition(numbers, elements);
cout << "\n\nSolution:\n";
printPartition(groupA, numbers, elements);
printPartition(~groupA,numbers, elements);
return 0;
}
изменить. Для дальнейших (и лучших) решений для генерации всех возможностей проверьте этот тент. Вот ссылка на книга knuths, которую я нашел здесь
edit2. Чтобы объяснить концепцию перечисления в соответствии с запросом:
предположим, что мы имеем три элемента, 1,23,5. все возможные комбинации без учета перестановок могут быть сгенерированы путем заполнения таблицы:
1 | 23 | 5 Concatination Decimal interpretation
-----------
0 | 0 | 0 000 0
0 | 0 | 1 001 1
0 | 1 | 0 010 2
0 | 1 | 1 011 3
1 | 0 | 0 100 4
1 | 0 | 1 101 5
1 | 1 | 0 110 6
1 | 1 | 1 111 7
Если теперь взять за мгновение число 4, это отобразится в 100, в котором говорится, что первое число находится в группе A, а второе и третье числа не являются (что означает, что они находятся в группе B). Таким образом, A 1, а B - 23,5.
Теперь, чтобы объяснить трюк, почему мне нужно только посмотреть на половину: если мы посмотрим на десятичную интерпретацию 3 (011 binary), мы получим для группы A 23,5 и для группы B 1. Если мы сравним это с примером для 4, мы заметим, что у нас одинаковые числа, сгруппированные, точно в противоположных именах групп. Поскольку это не имеет никакого значения для вашей проблемы, мы не должны смотреть на это.
Edit3:
Я добавил реальный код, чтобы попробовать, в псевдокоде я сделал неправильное предположение, что я всегда буду включать первый элемент в сумму, что было неправильно. Что касается вашего кода, на котором я начал: вы не можете выделять такие массивы. Другим решением вместо массива будет vector<int>, который избегает проблем передачи массива в функции. Использование этого было бы большим улучшением. Кроме того, этот код далек от хорошего. Вы столкнетесь с проблемами с int size (обычно это должно работать до 32 элементов). Вы можете работать над этим (возможно, как обращаться с произвольно большими целыми числами). Или вы на самом деле читаете на knuth (см. Выше). Я уверен, вы найдете какой-то рекурсивный подход.
Этот код также медленный, так как он всегда восстанавливает всю сумму. Одна из оптимизаций заключалась бы в том, чтобы взглянуть на серые коды (я думаю, Кнут описывает их также). Таким образом, вам нужно только добавить/вычесть одно число на каждую перестановку, которую вы тестируете. Это будет повышение производительности в порядке n, так как вы заменяете n-1 дополнениями с добавлением/вычитанием 1.