Разбить множество на три примерно одинаковые части

[zuj]

Доброго времени суток всем!

Имеется следующая задача.
Имеется конечное множество элементов $x_i\in X$.
Вопрос: Нужно разбить данное множество на 3 подмножества с условием чтобы сумма элементов в этих подмножествах была $\approx\frac{\sum^m_i x_i}{3}$ или переводя на русский надо распределить элементы между тремя множествами так чтобы сумма элементов во всех трех множествах была приблизительно равна.

Мне пока кроме "железобетонного" перебора ничего в голову не приходит. Алгоритм может быть примерно следующим:
1. Упорядочиваем элементы множества $X$ от наименьшего к наибольшему.
2. В каждое из 3 множеств кладем самые наибольшие элементы множества $X$.
3. Берем 4-ый с конца элемент и смотрим по очереди каждое из подможеств чтобы сумма имеющегося и добавляемого элемента не превосходила $\frac{\sum^m_i x_i}{3}$. Если не превосходит кладем элемент в это множество если превосходит, то берем следующее подмножество и так далее.
4. Так продолжаем пока сумма во всех подмножествах не приблизиться к желаемой $\frac{\sum^m_i x_i}{3}$.
5. Ну а остатки (если таковые имеются) раскидываем приблизительно одинаково по всем множествам.

Пример: $X=\{1,2,3,5,7,2,4,1,1,9\}$, следовательно $\frac{\sum^m_i x_i}{3}=11.7$
1. После упорядочивания получаем: $X={1,1,1,2,2,3,4,5,7,9}$.
2. Теперь кладем наибольшие элементы в подмножества $Y_1=\{9\}, Y_2=\{7\}, Y_3=\{5\}$.
3. Далее берем $x_7=4$. Явно он не подходит для множества $Y_1$ а вот для множества $Y_2$ в самый раз ... значит определяем его туда. Так и с остальными элементами ... получаем что $Y_1=\{9,2\}, Y_2=\{7,4\}, Y_3=\{5,3,2\}$.
4. Теперь остатки. По существу уже не важно в какое множество пойдут оставшиеся две 1 но пусть в первое и второе множества.
Итак получили, что $Y_1=\{9,2,1\}, Y_2=\{7,4,1\}, Y_3=\{5,3,2\}$ и соответственно $\frac{\sum Y_1}{3}=12$, $\frac{\sum Y_2}{3}=12$, $\frac{\sum Y_13}{3}=11$.

Вот такой вариант у меня имеется ... может кто нибудь подскажет что-нибудь умнее изложенного выше ... ну или хотя бы более эффективное.

[Mikhail Sokolov]

По-моему, это задача о разбиении или "о куче камней": известны количество и веса камней. Требуется распределить камни по $n$ ящикам так, чтобы вес самого тяжелого ящика был минимальным.
См., например, Романовский И.В. Алгоритмы решения экстремальных задач. М., 1977.

[mserg]

Можно сформулировать эту задачу как проблему линейного программирования. Только, конечно, нужно сгруппировать элементы одинакового размера чтобы уменьшить количество симметричных вариантов (т.е. использовать размеры и количества элементов этих размеров). С вероятностью 99.9% можно утверждать, что пакет линейного программирования среднего уровня даст результат лучше, чем любая самописная программа.

Что касается Романовской и задачи распределения камней, то эта проблема также легко формулируется в терминах линейного программирования. И тоже, линейное программирование "побъет" самописные программы. Ну, и если рассмотрить пример <3,3,6>, то решение <<>,<3,3>,<6>> для камней будет оптимальным, а для исходной задачи - нет: <<3>,<3>,<6>>.

Со мной, конечно, можно спорить, но реальные тесты все поставят на свои места.

P.S. Где-то год назад просматривал книжки по дискретной математике/дискретной оптимизации. Ни одной современной книги, просто каменный век - материалы 60-х годов! "Пипл хавает..."

[zuj]

Ну во-первых спасибо всем за ответы.

mserg писал(а):

Можно сформулировать эту задачу как проблему линейного программирования.

Я и сам интуитивно догадываюсь что эту задачу можо переформулировать в терминах линейного программирования только не особо понимаю как это сделать. Если есть идеи то с удовольствием выслушаю.

[mserg]

Можно, конечно, привести и линейную математическую модель, и данные, и решения. В чем тогда будет обучающий эффект, для которого создан данный раздел?

[zuj]

mserg писал(а):

Можно, конечно, привести и линейную математическую модель, и данные, и решения. В чем тогда будет обучающий эффект, для которого создан данный раздел?

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

[gris]

ув. zuj, можно немножко покритиковать Ваш метод?
11 10 7 7 7 7 7 7
В этом случае камни распределить можно с равными весами (21) ящиков. Но если вначале положить 10 и 11 в разные ящики, то такого распределения достичь нельзя будет.
Вам предусмотреть неизбежно придется возврат на шаг на любом этапе Вашего метода.
Я не знаю, если честно, как решать задачу, и это просто моё добродушное ворчание, а не злобная критика:)

[zuj]

gris писал(а):

ув. zuj, можно немножко покритиковать Ваш метод?

Покритиковать можно и даже нужно ибо это приводит к обнаружению ошибок. Вот как например в данной ситуации .

Тогда предлагаю небольшую модификацию к уже имеющемуся алгоритму:
На втором шаге вместо того чтобы просто разложить (будем называть их камнями, хотя это не обязательно) три самых крупных камня по кучкам, нужно проанализировать их попарную сумму и если окажется что она в районе той самой нас интересующей то складываем эти камни в одно множество а сами работаем в дальнейшем с двумя оставшимися. Ну конечно на последнем шаге когда приходит время распределять остатки опять берем в рассчет наше множество так беестыдно брошенное еще в начале алгоритма .

Ну как? Такой вариант чуть лучше?

[gris]

Мне кажется, что к задаче следует применять методы динамического программирования. С ним я знаком только на стандартных учебных задачах по распределению ресурсов, поэтому вряд ли могу дать хороший совет.
Но я думаю, что идея продвижения только вперёд неправильна. Должен быть механизм перераспределения даже первых трех камней. Иначе всегда можно подобрать соответствующий контрпример.
Хотя Ваш метод, наверное, будет хорошим приближением для практического использования в большинстве случаев. (Я не имею в виду камни, разумеется )

[zuj]

gris писал(а):

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

На тоже самое намекал mserg только не хочет признаваться как это сделать .

gris писал(а):

Хотя Ваш метод, наверное, будет хорошим приближением для практического использования в большинстве случаев.

Я тоже думал над этим и пожалуй соглашусь с Вами. Но за не именеем "аналитического решения" приходится довольствоваться тем что есть .

[gris]

Я имел ввиду динамическое программирование, хотя в этой задаче, по ходу, нужно именно линейное. А Вам еще примерчики:
5 5 5 3 3 3 3 3 3 3 3 3 3
10 9 8 3 2(15 штук)
А к тому же определите строго, что Вы собираетесь минимизировать? Сумму отклонений от среднего? Попробуйте порешать эту задачу для двух ящиков... Только вот я согласен, что доморощенные методы работать, скорее всего, не будут

[zuj]

gris писал(а):

А к тому же определите строго, что Вы собираетесь минимизировать? Сумму отклонений от среднего?

Сложно сказать ... мне казалось что минимизировать нужно сумму элементов каждого множества одновременно, что в свою очередь и является проблемой: как разложить элементы равномерно по всем множествам .

[gris]

я имею в виду, если у вас есть два разных распределения по ящикам, то как вы определите, какое лучше? Что будет показателем равномерности?
Например, массы ящиков стали: 1) 20 20 20 2) 17 19 24 3) 16 20 24
Ясно, что первый вариант идеальный. А какой лучше 2 или 3?
А из 1) 22 22 16 и 2) 20 16 24 ?

[zuj]

Пардон не сразу понял что Вы имели ввиду под

gris писал(а):

Сумму отклонений от среднего?

Я не знаю как ее минимизировать, но то что это является критерием при определении насколько хорошо мы распределили - это да.

gris писал(а):

Например, массы ящиков стали: 1) 20 20 20 2) 17 19 24 3) 16 20 24
Ясно, что первый вариант идеальный. А какой лучше 2 или 3?

Я думаю что 2 лучше чем 3 потому что хотя их суммарное отклонение и одинаково, но максимальное отклонение во 2-ом случае равно 3, а в 3-ем 4.

gris писал(а):

А из 1) 22 22 16 и 2) 20 16 24 ?

По логике вещей эти 2 случая выглядят равноценными, хотя я немного склоняюсь в пользу того что 1 случай поприятней (но это на уровне ощущений и никак не обосновано).

[worm2]

mserg в сообщении #155095 писал(а):

Что касается Романовской и задачи распределения камней, то эта проблема также легко формулируется в терминах линейного программирования.

Романовского не читал, но сомневаюсь в том, что рассматриваемая задача может быть сведена к задаче линейного программирования. В лучшем случае --- дискретного.
Дело в том, что задача ЛП полиномиально разрешима, а решение нашей задачи, помимо прочего, даст (ну хорошо, не обязательно даст, но вполне может дать ) ответ на вопрос: есть ли среди указанного множества чисел подмножество, сумма которого равна трети суммы всех чисел, т.е. частный случай NP-трудной задачи о сумме подмножеств.