Сумма с минимальным отклонением от среднего значения

Цитата
museum

Цитата
ridzhi
Я правильно понимаю, что это достаточно сложная задача ?)

Мне кажется, что неправильно. Мне кажется, что задача просто не поставлена, т.к. не указано, что именно минимизируется.
Начнем:
Имеется набор из m чисел (это число задано), нужно расположить их в n колонок (судя по тому, что Вы написали - это число тоже задано).
А вот это уже никуда не годится:

Цитата

чтобы разница в высоте относительно средней высоты колонки была минимальная

. Согласитесь, что найти

Цитата

три суммы элементов, с минимальным отклонением от 383,333.

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

Цитата
zklb (Дмитрий)

Цитата
vpro
Разумный перебор с отсечением заведомо негодных ветвей перебора называется методом ветвей и границ. Им и нужно воспользоваться. Думаю, что если исходное множество не превосходит нескольких сотен элементов, то такой перебор вполне реален.

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

Цитата
vpro

Цитата
zklb (Дмитрий)

Цитата
vpro
Разумный перебор с отсечением заведомо негодных ветвей перебора называется методом ветвей и границ. Им и нужно воспользоваться. Думаю, что если исходное множество не превосходит нескольких сотен элементов, то такой перебор вполне реален.

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

Пусть мы имеем $N$ чисел $a_i$. Их нужно разбить на $M$ групп так, чтобы суммы чисел $S_k, k=1,...M$ в группах удовлетворяли условию: $\max_k{|S_k-S_0|}\to \min$. Здесь $S_0=\frac1M\sum_{i=1}^N{a_i} $.
Рассмотрим полное дерево вариантов. В вершине дерева - $a_1$. Мы его можем поместить в одну из $M$ групп. Значит, из вершины выходит $M$ ветвей. Из каждой из этих ветвей исходит снова $M$ ветвей - в соответствии с возможным расположением второго числа.... И т. д. для каждого из $N$ чисел. Таким образом, построив дерево, мы получаем $M^N$ возможных вариантов.
Да, многовато...Поэтому начинаем отсекать лишние ветви. Для этого используем совершенно логичные соображения
1) Из соображений симметрии первый элемент достаточно оставить только в первой группе. Остальные $M-1$ вариантов его расположения мы смело можем отбросить. Так ведь? Мы сразу сократили дерево в $M$ раз. Второй элемент может попасть либо в группу к первому, либо в одну из свободных групп, например во вторую. Остальные варианты его размещения ($M-2$) отбрасываем.. И так далее....
2)Когда в первый раз достигаем некоторого варианта размещения (проходим дерево до конца по одному из путей), мы вычисляем показатель качества $F=\max_k{|S_k-S_0|}$. Строя дерево, мы также все время вычисляем накопленные суммы $S_k$ в каждой группе по каждому пути. Как только мы получим, что $|S_k-S_0|\ge F$, ветвь отбрасывается. Достигнув очередного варианта размещения, снова вычисляем $F$ и оставляем меньшее значение из старого и нового.

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

И никакой эвристики