Как классифицировать/сгруппировать элементы числового ряда так, чтобы сумма элементов в каждой группе была примерно одинаковой?

Question

[Александр]

Есть числовой ряд: 2717, 1995, 1633, 1244, 978, 745, 588 (чисел много больше).

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

Answer 1

[Wataru]

Это задача об оптимальном разбиении на подмножества, она NP-сложная. Тут нет какого-то простого и быстрого алгоритма.

Полный перебор, метод ветвей и границ, всякие методы отжига и генетические алгоритмы вам в помощь.

В отдельных случаях (сумма не очень большая и множеств всего 2; числа очень маленькие) возможны быстрые алгоритмы на основе динамического программирования

Comments

[Армянское Радио]

Почему же сюда не подходит k-means?

[Wataru]

Армянское Радио, Как вы себе его тут представляете вообще? Вот вам пример, 2 группы, числа: 1, 1, 10000, 10000.

Оптимальное разбиение {1, 10000}, {1, 10000}. Суммы 10001 и там и там. Ближе никак. Любой алгоритм кластеризации (в том числе и k-means) разобъет самым не оптимальным способом - {1,1}, {10000,10000} - суммы 2 и 20000. Не совсем "чтобы сумма элементов группы была максимально равной", как надо в автору.

[Армянское Радио]

Wataru, в k-means можно попробовать в качестве метрики выбрать сумму элементов в кластере. Не обязательно ведь его втупую применять.

[Wataru]

Армянское Радио, Ну вот вы сначала придумайте такую метрику. subset sum и кластеризация используют принципиально разные метрики. В сумме подмножеств метрика между группами целиком, а в кластеризации - между объектами. Если вы постараетесь как-то извратить метрику, то алгоритмы кластеризации перестанут работать.

Например, в k-means используется свойство, что если элемент близок к среднему в группе, то он в каком-то смысле ближе к каждому элементу в группе, чем к элементам других групп. Когда вы обобщите метрику на суммы в группах, это свойство потеряет всякий смысл.

[Армянское Радио]

Wataru, если подумать, можно сначала, например, свалить в кластеры похожие значения (что сделает обычный k-means), а потом из этих значений попытаться набалансировать нужные кучки с близкими суммами.

Успех авантюры зависит от того, сколько у автора данных (Автору - много это не оценка количества данных) и их статистического распределения.

[Wataru]

Армянское Радио, Ну вот в этом "из этих значений попытаться набалансировать нужные кучки" и состоит основная часть проблемы.

[Александр]

Спасибо, вам Армянское Радио , Wataru, участники дискуссии)

Успех авантюры зависит от того, сколько у автора данных (Автору - много это не оценка количества данных) и их статистического распределения.

Характеристика "много больше", а не просто "много" относилась к приведённому примеру - в реальной задаче их не 7 а 100. Нужно разбить эти 100 значений на группы (фиксированное количество, пусть на 6 групп), сумма элементов которых максимально возможно приближена к сумме элементов др.групп.

Я формулирую весьма понятийно. Знал бы структуры/алгоритмы в контексте задачи - выразился бы более точно)

Спасибо за советы и размышления.
Пойду читать про k-means

[Армянское Радио]

Александр, понимаете, под много мог скрываться и миллиард. А так, всего-то сто штук.

[Wataru]

Александр,

Пойду читать про k-means

Зря только время потратите. Лучше про метод ветвей и границ, да метод отжига почитайте.

[Wataru]

Армянское Радио,

под много мог скрываться и миллиард. А так, всего-то сто штук.

Для NP-полной задачи - 100 штук уже много, ибо любое решение так или иначе экспоненциально. Ну, если вы, конечно, доказали P=NP (с помощтю метода K-means с хитрой метрикой) - то напишите статью, получите несколько премий в миллион долларов и войдете в историю.

[Александр]

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

Еще раз спасибо!

[Армянское Радио]

Wataru, не слышали о таком факте, что человеку свойственно ошибаться? Тем более, что мы с вами на сайте с q&a а не в академическом учреждении, где все при галстуках. Да, я ошибся насчет применения k-means, и даже удалил свой ответ, какое еще наказание вы мне предложите?

[Wataru]

Армянское Радио, Слышали. Я вам сразу сказал, что вы не правы, но вы продолжили гнуть свою линию. Все мои комментарии вам - лишь ответ на ваши комментарии.