Алгоритм выделения списка номеров для N групп при определенных условиях

Question

Допустим, у меня есть список чисел:

2,2,3,4,4

Разбить числа на N групп (здесь в качестве примера 3 группы):

A:2,3 sum:5

B:4   sum:4

C:2,4 sum:6

Я хочу минимизировать группу с наибольшей суммой (6 здесь) - группу с наименьшей суммой (4 здесь).

Кто-нибудь думает об алгоритме для достижения этой цели?

---

Другой пример:

7,7,8,8,8,9,9,10

Результат должен быть следующим:

A:7,8,8 sum:23

B:7,8,9 sum:24

C:9,10  sum:19

Answer 1

К сожалению, эта проблема NP трудна. См. Ссылки для многопроцессорного планирования или упаковки бинов . Вы также можете найти некоторые полезные алгоритмы аппроксимации, если вы заинтересованы в этом подходе.

Answer 2

Учитывая, что если N равно двум, проблема в NP завершена, я могу дать вам очень плохой алгоритм.

http://mathworld.wolfram.com/NumberPartitioningProblem.html

Answer 3

Предложение Цвайтерлинде проверить упаковка бина - это путь.

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

Вам нужен жадный подход, при котором сначала используются самые большие числа.

1. сортировка списка для получения порядка
2. Начните размещать наибольшие числа в группы - столько, сколько потребуется для достижения первого числа
3. Останов, когда достигнуто максимальное количество групп
4. Сортируйте группы по сумме и повторите, добавив наибольшее число к наименьшей группе, повторяя до завершения.

Это должно дать вам: от 2,2,3,4,4 ...

group 1 (4): 4
group 2 (6): 4, 2
group 3 (5): 3, 2

и от 7,7,8,8,8,9,9,10 ...

group 1 (18): 10, 8
group 2 (24): 9, 8, 7
group 3 (24): 9, 8, 7

Хотя я предполагаю, что второй пример может быть сделан как 19, 24, 23, что делает это неправильно. Хммм.