[Математика] алгоритм нужен, сами мы не местные...

[Soul Eraser]

В программизме не силен, а математику помню крайне хреново - в силу чего возник следующий вопросик.


Имеется набор значений ( достаточно много ). Необходимо определить какое с какими складывать для получения наиболее равномерной суммы, причем количество финальных сумм оговаривается. :shock:

Грубо говоря есть a, b, c, d, e, f, g. И необходимо три суммы.
От алгоритма надо получить на выходе ответ наподобие "складывать надо так: a+c, b+d+f+g, e - будет примерно равно".

Может ли кто-либо ( хитро косясь в сторону stellar-а ) ткнуть моим глупым носом в алгоритм? :alive:

Запрограммить-то я его запрограммлю, еще не совсем отупел.

[Demon™]

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

[DJ Lox++]

Все просто:

допустим размерность вектора значений Y = n
кол-во сумм f = m
тогда имеем матрицу A размерности [m*n], состоящую из нулей и единиц, а общее число единиц равно n, и следующее уравнение:

A*Y = F

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

и смело решаем задачу минимизации целевой функции путем перестановки единичек в матрице A :idea:

если не перебирать все возможные комбинации, то появляется два вопроса:
-как это сделать оптимально быстро?
-критерий останова?

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

[DJ Lox++]

После некоторых раздумий... :idea:

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

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

А еще проще: задачу в студию!!!

[Soul Eraser]

Да задача в общем тупая до невозможности.

Имеется n файловых систем различной степени заполненности. Надо в четыре потока их бекапить, причем размеры потоков должны быть поодинаковей, ибо только при более чем трех одновременных потоках удается подать на LTO приводы данные со скоростью которая этим LTO необходима ( LTO1 - 15 MB/sec, LTO2 с картриджами LTO1 - 20Mb/sec ).

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