Разбиение списка целых чисел для минимизации разности их сумм

Задан список целых чисел l, как я могу разбить его на 2 списка a и b таким образом, что d(a,b) = abs(sum(a) - sum(b)) является минимальным. Я знаю, что задача NP-полная, поэтому я ищу алгоритм псевдополиномиального времени, т. е. O(c*n), где c = sum(l map abs). Я посмотрел наWikipedia , но алгоритм там состоит в том, чтобы разбить его на точные половины, что является частным случаем того, что я ищу...

Править: Чтобы уточнить, я ищу точные разделы a и b, а не только результирующий минимальная разница d(a, b)

Чтобы обобщить, что такое алгоритм псевдополиномиального времени для разбиения списка n чисел на k группы g1, g2 ...gk такие, что (max(S) - min(S)).abs как можно меньше, где S = [sum(g1), sum(g2), ... sum(gk)]

3 3
algorithm big-o dynamic-programming np-complete

3 ответа:

Наивным, тривиальным и все еще псевдополиномиальным решением было бы использовать существующее решение для подмножества-суммы и повторить для sum(array)/2до 0 (и вернуть первое найденное).

Сложность этого решения будет O(W^2*n), где W - сумма массива.

Псевдокод: 

for cand from sum(array)/2 to 0 descending:
   subset <- subsetSumSolver(array,cand)
   if subset != null:
        return subset

Выше будет возвращено максимальное подмножество, которое меньше / равно sum(array)/2, а другая часть является дополнением для возвращаемого подмножества.

Однако , динамическая программирования для подмножества-суммы должно быть достаточно.

Напомним, что формула такова: 

f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)

При построении матрицы вышеописанное фактически создает вам каждую строку со значением ниже начального x, Если вы вводите сумму(массив)/2 - это в основном все значения.

После того, как вы сгенерируете матрицу DP, просто найдите максимальное значение x такое, что f(x,n)=true, и это лучшее разбиение, которое вы можете получить.

Сложность в этом случае равна O(Wn)

2

Можно сформулировать это как задачу оптимизации целочисленного линейного программирования 0/1. Пусть wi-это I-е число, а xi-переменная 0/1, указывающая, входит ли wi в первый набор или нет. Затем вы хотите минимизировать сумму(Си Висконсин) - сумма((1 - ХІ) Висконсин) при условии

Сумма(ХІ Висконсин) >= сумма((1 - ХІ) Висконсин)

, а также при условии, что все xi равны 0 или 1. Было проведено много исследований по оптимизации решателей линейного программирования 0/1. Для большой общей суммы W это может быть улучшением по сравнению с O(W Н) псевдо-полиномиальное время представлен алгоритм, потому что W фактор-это страшно.

0

Моя первая мысль:

  1. сортировка списка целых чисел
  2. Создайте два пустых списка A и B
  3. при итерации от наибольшего целого числа к наименьшему целому числу...добавьте следующее целое число в список с наименьшей текущей суммой.

Это, конечно, не гарантирует вам наилучший результат, но вы можете ограничить результат, который он даст вам, размером самого большого целого числа в вашем списке

-1