Разделите заданный набор чисел N в двух группах, чтобы их разность их суммы была минимальной?

Question

Вы можете освободить один из элементов из набора, чтобы достичь цели. пример: -

N = 3

числа даны = 1,2,5

Так,

Набор 1 должен быть: - [1]

Набор 2 должны быть: - [2]

Мы исключили 5, поскольку мы можем добиться меньшего разницы, не будучи в обеих группах.

N = 4

числа = 1,2,2,5

Set1 = [1,2,2]

Set2 = [5]

Что лучше алгоритм для этого? Я знаю, что это NP-полная проблема. И я думаю, что грубая сила дала бы мне правильное решение, но мне нужен алгоритм, если он доступен.

Answer 1

Я знаю, что это NP-полной задачи.

Непонятно, что partition optimisation problem известен как NP-жесткий.

И я думаю, что грубая сила даст мне правильное решение, но мне нужен алгоритм, если он доступен.

NP-hard означает, что нет известного алгоритма (для определения решения), который лучше, чем метод грубой силы.

Так что вам, вероятно, понадобится approximation, но который подходит только вам, только вы можете знать.

Что является лучшим алгоритмом для этого?

Определите «лучший».

Answer 2

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

Поскольку исходная проблема NP-полная, она тоже NP-полная (на самом деле это оптимизационная версия проблемы, которая даже NP-hard, как правильно сказано в ответе Берги). Хорошая новость заключается в том, что даже в этой более сложной версии жадный подход может дать вам удовлетворительный ответ в большинстве случаев. Стратегия такова: возьмите самые большие элементы из исходного набора и поместите их в первое и второе подмножество, по одному в каждом из них. Каждый другой элемент из исходного набора помещается в подмножество, сумма которого меньше и повторяет процедуру итеративно, пока вы не выберете все элементы.

Для достижения наилучшего результата вам потребуется повторить эту процедуру для всех N подмножеств исходного набора, где вы получите каждое подмножество, удалив элемент с индексом 1,2, ..., N. Это еще больше усложняет эту проблему.

Если вас интересует более продвинутый подход, взгляните на Karmarkar-Karp differencing algorithm.

Смотрите также:

• The easiest hard problem