Дан ряд случайных чисел. Необходимо его разделить на 2 так, чтобы сумма чисел в каждом из них была одинакова. Простым перебором слишком долго. Может, кто подскажет метод побыстрее?
Заранее спасибо.

Сумма чисел где?

Сумма чисел в каждом из полученных рядов.
Например есть ряд: 1, 2, 3, 4, 6, 7, 8, 9.
Первый ряд: 1, 2, 8, 9. Сумма 20
Второй ряд: 3, 4, 6, 7. Сумма 20

исходя из условия у нас есть две суммы А и Б и что что А=Б=общая_сумма/2

То есть Задача сводится к нахождению группы чисел, которая в сумме даст А.

Придётся таки все перебирать на это условие. Это вроде один из подразделов "магического" квадрата. Там тоже только перебор. Но это лучше, чем перебирать по начальному условию.

Ограничения, если числа сгенерены случайно.
Решение отсутствует, если:
Общая сумма всех чисел не кратна 2.
Все числа позитивны и присутсвует число Х, и Х > А -> Разделить будет невозможно.
Добавлено @ 02:27

В йтом примере будет работатьтак:

summa= 1+2+3+4+6+7+8+9; //=40;
A=summa/2; //=20

Осталось найти, какие числа из 1, 2, 3, 4, 6, 7, 8, 9 в сумме дадут 20

А если A число нечетное, то можно подумать над тем не лепить ли его из нечетных чисел сначала, а лишь потом если не получится работать с четными. Ну и если А четное, то соответственно наоброт.
В данном случае А = 20 значит идем и складываем все четные числа
2+4+6+8... о 20 значит больше ничего делать не надо.

только вопрос, возможны ли там негативные числа также и/или одинаковые

Я считаю что все просто:
Сортируешь ряд исходных чисел, потом первое и последнее счисло в ряд1, второе и предпоследнее в ряд2, третье и ... в ряд1 ит.д.
Потом уже перебором корректируешь эти ряды.
Для ряда 1 2 3 4 5 6 7 8 9 будет так:
ряд1: 1 9 3 7
ряд2: 2 8 4 6
Корректировки в данном случае не нужны.
В другом случае могут быть.
Добавлено @ 05:59

Да. Если это так, то корректировки делать бесполезно.

Ну блин же ж... задача о рюкзаке в чистейшем виде... чего спрашивать-то?

Это что такое?
И как решать тогда?

только перебор это классическая НП полная задача

Поиск никто не отменял. В т.ч. в Инете.


NP-полная задача с временем O(n)??? ну-ну..

http://www.cs.brown.edu/courses/cs051/assign/hw10.sol.ps


Посмотрите тут вторую задачу. Она НП полная, но в то жевремя немного проще задачи, решенной вами за линейное время.

Видимо вы доказали что НП=П.

Поздравляю.


с уважением