Полный перебор, метод ветвей и границ, всякие методы отжига и генетические алгоритмы вам в помощь.
В отдельных случаях (сумма не очень большая и множеств всего 2; числа очень маленькие) возможны быстрые алгоритмы на основе динамического программирования
Армянское Радио, Как вы себе его тут представляете вообще? Вот вам пример, 2 группы, числа: 1, 1, 10000, 10000.
Оптимальное разбиение {1, 10000}, {1, 10000}. Суммы 10001 и там и там. Ближе никак. Любой алгоритм кластеризации (в том числе и k-means) разобъет самым не оптимальным способом - {1,1}, {10000,10000} - суммы 2 и 20000. Не совсем "чтобы сумма элементов группы была максимально равной", как надо в автору.
Армянское Радио, Ну вот вы сначала придумайте такую метрику. subset sum и кластеризация используют принципиально разные метрики. В сумме подмножеств метрика между группами целиком, а в кластеризации - между объектами. Если вы постараетесь как-то извратить метрику, то алгоритмы кластеризации перестанут работать.
Например, в k-means используется свойство, что если элемент близок к среднему в группе, то он в каком-то смысле ближе к каждому элементу в группе, чем к элементам других групп. Когда вы обобщите метрику на суммы в группах, это свойство потеряет всякий смысл.
Wataru, если подумать, можно сначала, например, свалить в кластеры похожие значения (что сделает обычный k-means), а потом из этих значений попытаться набалансировать нужные кучки с близкими суммами.
Успех авантюры зависит от того, сколько у автора данных (Автору - много это не оценка количества данных) и их статистического распределения.
Успех авантюры зависит от того, сколько у автора данных (Автору - много это не оценка количества данных) и их статистического распределения.
Характеристика "много больше", а не просто "много" относилась к приведённому примеру - в реальной задаче их не 7 а 100. Нужно разбить эти 100 значений на группы (фиксированное количество, пусть на 6 групп), сумма элементов которых максимально возможно приближена к сумме элементов др.групп.
Я формулирую весьма понятийно. Знал бы структуры/алгоритмы в контексте задачи - выразился бы более точно)
Спасибо за советы и размышления.
Пойду читать про k-means
под много мог скрываться и миллиард. А так, всего-то сто штук.
Для NP-полной задачи - 100 штук уже много, ибо любое решение так или иначе экспоненциально. Ну, если вы, конечно, доказали P=NP (с помощтю метода K-means с хитрой метрикой) - то напишите статью, получите несколько премий в миллион долларов и войдете в историю.
Wataru, не слышали о таком факте, что человеку свойственно ошибаться? Тем более, что мы с вами на сайте с q&a а не в академическом учреждении, где все при галстуках. Да, я ошибся насчет применения k-means, и даже удалил свой ответ, какое еще наказание вы мне предложите?
Армянское Радио, Слышали. Я вам сразу сказал, что вы не правы, но вы продолжили гнуть свою линию. Все мои комментарии вам - лишь ответ на ваши комментарии.
