Разделение ценностей по группам равномерно

Question

Позвольте мне попытаться объяснить ситуацию как можно лучше.

Допустим, у меня есть 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

Обратите внимание, что колонны не тихие даже, но они настолько близко, насколько это возможно. Чуть-чуть-чуть-чуть-чуть считается нормальным, при условии, что список так близок, что это возможно

У кого-нибудь есть предложения? Знаешь какие-нибудь хорошие способы сделать это?

Answer 1

Я бы сделал это так:

• добавьте все значения, назовем это S
• разделите S на количество столбцов, назовем это M.
• найдите набор значений, сумма которых равна M или максимально приближена к M, используя алгоритм ранца (например, http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack.pm (просто быстрый Google на ранце))
• взять сумму набора значений и вычесть ее из S, назовем ее T.
• делим T на количество столбцов минус 1
• и повторите алгоритм

Answer 2

Я ответил на похожий вопрос некоторое время назад.

Я могу придумать жадное субоптимальное решение.

1. Сортировка чисел в порядке убывания. (меньшие числа удивляют меньше, поэтому разберитесь с ними позже)
2. Определитесь с количеством комплектов, которые у вас будут. не слишком уверен в этом
3. Просмотрите элементы набора один за другим и поместите их в подмножество с наименьшей суммой (циклический перебор в случае равных сумм)

Это никогда не даст вам оптимального решения.

В вашем случае заказ будет 8 7 4 3 1. И вы (к счастью) получите те же результаты, о которых упоминали.

8 = 8

7 1 = 8

4 3 = 7

Это не всегда даст вам оптимальное решение

Answer 3

Если вы хотите точно такие же значения, то для числа столбцов x = 2 это классическая проблема разбиения , которая является NP-полной, но имеет псевдополиномиальные решения.

Anyбольше столбцов (то есть x> 2), и он становится сильно NP-Complete. Проблема с 3 разделами .

Я подозреваю, что для x> 3 он все еще будет сильно NP-Complete.

Поскольку проблема с x-разделением может быть сведена к вашемупроблема, это будет так же сложно, как и вышеупомянутые проблемы.

Возможно, вам понадобятся эвристические методы, чтобы помочь вам.