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

РЕДАКТИРОВАТЬ: Чтобы уточнить, я ищу точные разделыa а такжеb а не только полученная минимальная разницаd(a, b)

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