Разделение значений в группы равномерно
Позвольте мне попытаться объяснить ситуацию лучшее, я могу.
Позволяет говорят, что у меня есть 3 значения
1, 2, 3
Я говорю алгоритму разделять, это оценивает в x столбцы. Позволяет говорят x = 2 для разъяснения.
Алгоритм решает, что группа значений лучше всего помещается в два столбца следующий путь.
1st column 2nd column
---------------------------
1 3
2
Каждый столбец имеет четное число (общие количества, не литералы) значение.
Теперь позволяет, говорят, что у меня есть следующие значения
7, 8, 3, 1, 4
Я говорю алгоритму, что хочу значения, разделенные на 3 столбца. Алгоритм теперь говорит мне, что следующее является лучшим соответствием.
1st column 2nd column 3rd column
8 7 3
1 4
Заметьте, как столбцы не тихи даже, но это настолько близко, как это может добраться. Немногим более, чем и немного под рассматривается хорошо, пока списком является AS БЛИЗКО К КАК РАЗ КОГДА IT CAN БЫТЬ.
Кто-либо получил какие-либо предложения? Знать какие-либо хорошие методы выполнения этого?
3 ответа
Я бы сделал это так:
- сложите все значения, назовем это S
- разделим S на количество столбцов, назовем это M.
- найдите набор значений, сумма которых равна M или максимально приближена к M, с использованием алгоритма ранца (например, http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack .pm (просто быстрый поиск в Google на рюкзаке))
- возьмите сумму набора значений и вычтите ее из S, назовем это T.
- разделите T на количество столбцов минус 1
- ] и повторите алгоритм
Если вам нужны точно такие же значения, то для числа столбцов x=2, это классическая Partition Problem, которая является NP-полной, но имеет псевдополиномиальные решения.
Если столбцов больше (т.е. x>2), то она становится сильно NP-полной. 3-Partition Problem.
Для x > 3, я подозреваю, она все еще будет сильно NP-полной.
Поскольку проблема x-разбиения может быть сведена к вашей проблеме, она будет такой же трудной, как и вышеперечисленные проблемы.
Вероятно, вам понадобятся эвристические методы, чтобы помочь вам.
Некоторое время назад я отвечал на аналогичный вопрос.
Я могу придумать жадное неоптимальное решение.
- Отсортируйте числа в порядке убывания. (меньшие числа удивляют меньше, поэтому разберитесь с ними позже)
- Решите, сколько наборов у вас будет. не слишком уверен в этом
- Просмотрите элементы набора один за другим и поместите их в подмножество с наименьшей суммой (циклический перебор в случае равных сумм)
Это никогда не даст вам оптимального решения, хотя .
В вашем случае 8 7 4 3 1 будет порядком. И вы (к счастью) получите те же результаты, что и упомянули.
8 = 8
7 1 = 8
4 3 = 7
Это не всегда даст вам оптимальное решение