Разделение предметов по весу

[niki123]

Здравствуйте.
Подскажите алгоритм решения вот такой задачи.

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

Я как то не совсем понимаю как организовать перебор значений.

[Smitt&Wesson]

Перебор сдесь не поможет. При большом количестве предметов возникнет "информационный фзрыв". Поступают примено так:
Массив, сортируется по весам
Выбираются два самых тыжеловесных предмета и суммируются в две переменные.
Из оставшихся, опять беруться два и к самому лёгкому (лёгкой группе) из уже образованных, добавляется самый тыжёлый.
Так поступаем до опустошения исходного массива.
Веса полученных, будут макимально равны.

[pproger]

2Smitt&Wesson
у этого алгоритма есть название? просто интересно. с виду какой то жадный алгоритм равномерного распределения)

[Smitt&Wesson]

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

2Smitt&Wesson
у этого алгоритма есть название? просто интересно. с виду какой то жадный алгоритм равномерного распределения)

Да, согласен, жадноват он (названия не помню, просто где-то вычитал). Эту задачку можно решить, например, целочисленным симплекс-методом, но он в реализации довольно сложен, а этот "жадный" очень просто решить при помощи одного массива и двух реременных.

[niki123]

Спасибо за ответ.

Из оставшихся, опять беруться два и к самому лёгкому (лёгкой группе) из уже образованных, добавляется самый тыжёлый.

"Беруться два" тяжелый добавляется к легкой группе, а легкий добавляется к тяжелой группе? Но тогда алгоритм работать не будет или я что то не так понял.

[Smitt&Wesson]

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

Спасибо за ответ.

"Беруться два" тяжелый добавляется к легкой группе, а легкий добавляется к тяжелой группе? Но тогда алгоритм работать не будет или я что то не так понял.

Вы всё правильно поняли. Почему не будет? Поэкспериментируйте с монетками разного достоинства.

[Serge_Bliznykov]

niki123, задачу эту для чего решаете? (цель какую пытаетесь достигнуть, какой результат получить? ) N какой максимальной величины может быть?

Дело в том, что оптимальное решение может дать ТОЛЬКО перебор!
Все остальные методы могут дать тольк весьма и весьма приближённое к оптимальному...

Сообщение от Smitt&Wesson

Вы всё правильно поняли. Почему не будет?

Smitt&Wesson, распишите, пожалуйста, Ваш алгоритм на простейшем примере.
есть веса: 15 11 8 8 8 2
очевидно, что решение две кучки по 26 (15+11) и (8+8+8+2)
а по Вашему алгоритму как получается?

[onewho]

из его решения выходит 25 и 27,
этот алгоритм по-моему неплох, при увеличении количества элементов, разница между группами (по отношению к размерам групп) будет если не уменьшаться то невелика

[Serge_Bliznykov]

onewho, ага. а если взять 17 15 11 11 10 (разделение по 32: 17+15 и 11+11+10), то алгоритм даст 17 + 11 = 28 и 15+11+10=36 - отклонение в 4 единицы при оптимальном распределении 32 единицы. 12.5% погрешность..

Впрочем. согласен, если не стоит задача найти оптимальное распределение - то алгоритм крайне эффективен и вполне может быть использован практически. (тем более, что для сравнительно больших N результат перебор может занять ОЧЕНЬ продолжительное время!)

[Smitt&Wesson]

Разделить эти предметы на две группы так, чтобы общие веса групп были максимально близки.

По условию задачи, именно максимально близки, а не оптимальны.
Для оптимального решения (кроме перебора) существует алгоритм "поиск с возвращениями" на гра'фе.
Я тоже о нём подумал вначале, но учитывая уровень подготовки топикстартера и условие задачи, предложил именно этот.
Он не так эффективен, зато прост в реализации. Да и по скорости он быстрее чем обход графа.