Архив форумов ЦИТФорума

[vitek74]

Всем откликнувшимся, ПРИВЕТ!
Помогите или направьте...
Нужно из 1-го числового массива создать 3 массива примерно равные по сумме значений.
Это необходимо для подсчета баланса мощностей в однофазной сети. Есть общая мощность которую нужно раскидать по фазам (А,В,С) так чтобы нагрузка на фазах была равномерной.
Что-то я сам не могу придумать алгоритм... (туплю наверное )

[Bjorndalen]

3 новых массива должны быть равного размера?

[Alex_soldier]

Поделить на 3 массива, посчитать суммы, а потом парными заменами попытаться выровнять их.
P.S. Если не изменяет память, это называется Метод Потенциалов!
_________________
Мир Идей

[b1ood]

Как вариант

массив 1: max_1 max_6 max_7 max_12 .....
массив 2: max_2 max_5 max_8 max_11 .....
массив 3: max_3 max_4 max_9 max_10 .....

max_1 - самое максимальное, max_2 - максимальное из оставшихся

[Kefir]

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

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

Если же нагрузок много, качество решения должно быть высоким, а вычислительных ресурсов мало, то придется прибегнуть к генетическим алгоритмам. Хотя, это, как правило, лишнее...
_________________
Самоловских Виталий aka Kefir

[vitek74]

[Kefir]

Эвристические алгоритмы не являются алгоритмами, приводящими к точному решению задачи. Они основаны на интуиции и опыте.

Генетические алгоритмы - это своего рода модель естественного отбора. На первом этапе получают ряд произвольных решений задачи. Из них отбираются наиболее удачные. Из них при помощи комбинирования признаков этих решений и внесения новых (мутаций) получают новые решения. Процесс повторяется много раз.
_________________
Самоловских Виталий aka Kefir

[Yello]

Kefir, вопрос к Вам:
А сама задача случайно не является ли ЗАДАЧЕЙ ОПТИМИЗАЦИИ (раз уж Вы много знаете... )
Т.е нам ведь нужно минимизировать |s1-s2| + |s2-s3| + |s3-s1|?
(может, даже третье слагаемое можно выкинуть).

[Kefir]

Является.

Можно такой функционал:

max(s)-min(s)

предложить.
_________________
Самоловских Виталий aka Kefir

[Alex_soldier]

Да, самое главное: а каков размер задачи?
При некотором пороговом количестве элементов искать решение точными методами становится просто бессмысленно!
Уточню: каков порядок N = (количество элементов)
_________________
Мир Идей

[Kefir]

Очевидно m^n, гед m - число массивов, n - число нагрузок, ^ - степень числа.
_________________
Самоловских Виталий aka Kefir