Разложить k элементов по n массивов так чтобы сумма элементов в каждом массиве стремилась к m

это NP-полня задача, так что.... Brunch&Bound, тупой перебор, Лагранжева релаксация и т.п.

:'(

Точно? Как-то это больно на PHP для веба. То, что у меня все значения в приблизительно заранее известном диапазоне, мне никак не поможет?

Точно?

точно. Если не веришь мне, посмотри на вики.

Как-то это больно на PHP для веба. То, что у меня все значения в приблизительно заранее известном диапазоне, мне никак не поможет?

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

Это изветсная задача. Subset Sum Problem.

Спасибо. Пошел читать. Конечно же мне оптимального решения не надо. Надо «как нибудь». Дизайнер, сцуко придумал хитрую мозаику.

стремилась к m

была меньше m и как можно ближе к нему

а поточнее? что значит «ближе к m» с учетом того, что этих сумм несколько? что лучше при m=200:

[ 101+98 , 102+97 ]
или
[ 102+98, 101+97 ]

Из примера лучше первое. На самом деле при m'<m лучше вариант при котором (m-m')/n было бы минимальным (n - количество элементов отобранных для получения m'). Пусть это оценка будет P (т.е. P=(m-m')/n) тогда лучшее разбиение это где произведение всех P минимальна. Я так думаю.

http://joxi.ru/7-P_U_3JTJAENbT_rg0 - каждая строка это группа. Числа на оранжевых табах слева - это как раз P каждой группы. Последняя группа с P==3.75 выброшена как уже очень плохая, поэтому строк меньше чем табов.

произведение всех P минимальна

в таком варианте, если одно из P = 0 равно нулю, получаем идеальное распределение независимо от остальных P

обычно минимизируется сумма квадратов, реже - сумма модулей

Не придирайся. Понимаешь же, что P+1. Ну а так, правильно, да - сумма квадратов. Сумма модулей выглядит не очень хорошим решением.

А у задачи есть какое-то название? Чтобы нагуглить.

Точно?

Это задача о рюкзаке с дискретными весами.

Задача о наполнении рюкзака.

ну, про P+1, извини, сам я не догадался )

математика не нужна программисту кокок

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