проблема с пользовательским разделом

Question

Может ли кто-нибудь подсказать мне, как решить эту проблему.

Нам дан набор S с k числом элементов в нем.

Теперь мы должны разделить набор S наx подмножеств, так что разница в количестве элементов в каждом подмножестве не превышает 1, а сумма каждого подмножества должна быть как можно ближе друг к другу.

Пример 1: {10, 20, 90,200, 100} нужно разделить на 2 подмножества

Решение: {10,200} {20,90,100}

сумма равна 210 и 210

Пример 2: {1,1, 2, 1, 1, 1, 1, 1, 1, 6}

Решение: {1,1,1,1,6} {1,2,1,1,1}

Сумма 10 и 6.

Answer 1

Я вижу возможное решение в два этапа.

Первый этап

Начните с выбора количества подмножеств, N. Сортируйте исходный набор, S, есливозможный.Распределите самые большие N чисел из S в подмножества с 1 по N по порядку.Распределите следующие N самых больших чисел из S подмножеств в обратном порядке, от N до 1. Повторяйте, пока все числа не будут распределены.

Если вы не можете отсортировать S, распределите каждое число из S в подмножество (илиодно из подмножеств) с наименьшим количеством записей и наименьшим итогом.

Теперь у вас должно быть N подмножеств, все размером в пределах 1 друг от друга и с очень примерно одинаковыми итогами.

ЭтапДва

Теперь попробуйте уточнить примерное решение, которое у вас есть.Выберите наибольшее общее подмножество L и наименьшее общее подмножество M. Выберите число в L, которое меньше числа в M, но не настолько, чтобы увеличить абсолютную разницу между двумя подмножествами.Поменяйте местами два числа.Повторение.Не все пары подмножеств будут иметь заменяемые числа.Каждый своп поддерживает подмножества одинакового размера.

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

Вы можете чередовать этапы, если в некоторых подмножествах есть хотя бы два члена.

Answer 2

Нет простого алгоритма для этой проблемы.

Ознакомьтесь с проблемой разбиения , также известной как самая простая трудная задача , которая решает эту проблему за 2 подхода. Эта проблема является NP-Complete, и вы должны быть в состоянии найти все алгоритмы для ее решения в Интернете

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

Например:

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

{a1 ... ak} is your set

For i = 2 to k:

   try to solve the following program:
        xjl = 1 if element j of set is in set number l (l <= i) and 0 otherwise

        minimise max(Abs(sum(apxpn) -sum(apxpm)) for all m,n) // you minimise the max of the difference between 2 sets.

        s.t 
        sum(xpn) on n = 1
        (sum(xkn) on k)-(sum(xkm) on k) <= 1 for all m n // the number of element in 2 list are different at most of one element.
        xpn in {0,1}

  if you find a min less than one    then stop
  otherwise continue

end for

Надеюсь, мои записи понятны.

Сложность этой программы экспоненциальная, и если вы найдете полиномиальный способ решения этой проблемы, вы будете проверять P = NP, поэтому я не думаю, что вы можете добиться большего успеха.

---

РЕДАКТИРОВАТЬ

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

---

РЕДАКТИРОВАТЬ 2

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

Надеюсь, на этот раз проблема полностью понятна, хотя это решение может быть неоптимальным

Answer 3

Я не ученый, поэтому я бы попробовал два подхода:

После сортировки элементов, затем с обоих «концов» и перемещения первого и последнего к фактическому набору, затем переход к следующему набору, цикл;

Тогда:

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