Олимпиадная задача

[Sanek_ntsk]

Имеется N предметов, веса которых соответственно равны a1, a2, ... an. Разделить эти предметы на 2 группы так, чтобы общие веса групп были максимально близки.

Не могу решить эту задачу. Не знаю даже с чего начать. Была идея раскидывать грузы по очереди, то есть каждый раз смотреть в какой группе меньше сумма грузов, туда груз и добавлять, но это не правильно.
Пример грузов: 25, 16, 9, 36, 41. Правильный ответ: 1я группа - 25+41=66. 2я группа - 16+9+36=61. При сортировке что по возрастанию, что по убыванию правильного ответа не получается.

[Son Of Pain]

Тут нет алгоритма кроме перебора.

[gaw4]

а что если так
1 определяем средний вес (25+ 16+ 9+ 36+ 41)/2=63,5
2 полный перебор:
--- сумма до первого превышения ср веса
------сумма оствышихся
--------если разность меньше предыдущей --- запомнить наборы

[Mandrivnyk]

Уже обсуждалась эта задача тут.
Поищи...

[Serge_Bliznykov]

Сообщение от Son Of Pain

Тут нет алгоритма кроме перебора.

никогда не говори никогда...
почитайте тему по ссылке ниже..

Сообщение от Mandrivnyk

Уже обсуждалась эта задача тут.
Поищи...

угу. было такое дело.
я поискал.
вот она - Разделение предметов по весу

пост #2 (c) Smitt&Wesson в данной теме даёт нужный алгоритм.

p.s. алгоритм крайне простой и эффективный. Единственный недостаток - он не всегда даёт оптимальное решение.
Зато он всегда даёт решение чтобы "общие веса групп были максимально близки"