Проблема Разделения

Question

У меня есть набор неуникальных чисел, и я хотел бы разбить эти числа на K разделов так, чтобы сумма чисел в каждом разделе была почти равна. Предположим, у меня есть следующий набор.

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Использование Алгоритм линейного разбиения Я получаю следующие разделы, когда K = 3

{ 1  2  3  4  5 }
{ 6  7 }
{ 8  9 }

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

Разница суммы элементов для каждого раздела должна быть минимизирована. В приведенном выше примере сумма каждого раздела составляет 15, 13, 17

для следующего ввода не работает.

{10, 20, 90, 100, 200}

Алгоритм линейного разбиения дает мне следующее

{ 10  20  90  100 }
{ 200 }

Но правильный ответ должен быть

{ 10, 200 } { 20, 90, 100 }

Answer 1

Вот быстрое жадное решение (почти оптимальное для большинства случаев):

1. Сортировка элементов в порядке убывания
2. Возьмите первые K элементы и поместите их вразличные наборы
3. Для следующих N-K элементов поместите их в набор с наименьшей суммой

В вашем случае с {10, 20, 90, 100, 200}, после сортировки вы получите {200, 100, 90, 20, 10}.Алгоритм будет проходить следующим образом:

Set A   Set B
 200     100
 200     190
 200     210
 210     210

, что является оптимальным решением.

Answer 2

Я думаю, что в значительной степени единственный вариант, который у вас есть, - это использовать грубую силу, возможно, с некоторыми оптимизациями (например, модифицированную версию псевдополиномиального решения проблемы подмножества сумм для K = 2) для простые случаи. Может быть, есть лучший алгоритм, но не намного лучше.

Из чтения статей Википедии по Проблема с разделами и Проблема с 3 разделами , я понял, что ваша проблема является обобщенной и слегка измененной версией этих проблем, которые являются NP-полными.

Более конкретно, если бы у вас был эффективный алгоритм для решения вашей проблемы, он также мог бы эффективно решить две вышеупомянутые проблемы, что невозможно (если P = NP).

Answer 3

LeetCoder работал над тем же определением проблемы (и решением), которое предоставил Стивен Скиена. Единственное, что он говорит на C ++, так что становится легче понять.

Answer 4

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

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