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

[grayrat]

Здравствуйте! На работе (инженер BSS в Мегафоне) образовалась одна задача, не вдаваясь в подробности её появления, переформулирую её в привычных попугаях, не меняя сути.

Есть n камешков произвольной массы. Есть также m<n банок. Нужно максимально оптимально распределить камешки по банкам таким образом, чтобы массы банок были максимально равны между собой. В качестве целевой функции можно взять среднеквадратическое отклонение масс банок от среднего и его минимизировать. Количества камешков в банках не обязано быть равным.

Пока эти "камешки" мы "перекладываем" на глазок, этого в принципе достаточно, но во-первых хочется процесс автоматизировать, чтобы компьютер сам думал, во-вторых задачка просто вызвала у меня интерес. Я её уже частично решил, локальные минимумы я нахожу, этого тоже в принципе достаточно. Но хочется найти идеал - добиться поиска глобального минимума. Решаю так: либо сразу организую заполнение банок таким образом, чтобы по крайней мере в первых банках оказалась масса минимально отличающаяся от средней. Или сперва раскладываю камешки произвольно по n/m в банку (или даже тасую их через rnd), а потом, последовательно применяя свопы и перемещения, добиваюсь минимума СКО. В обоих алгоритмах использую рекурсию.

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