Проблема раздела

У меня есть набор уникальных чисел и хотел бы разбить эти числа на разделы 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 }

Ответ 1

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

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

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

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

который оказывается оптимальным решением.

Ответ 2

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

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

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

Ответ 3

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

Конечно, это может повредить вашу сложность во время выполнения, но я не видел, чтобы это было требованием.

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

Ответ 4

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