У меня есть проблема, которая является разновидностью проблемы с разделами, которая является NP-полной. Это проблема оптимизации, а не проблема принятия решения.
Задача: разбить список чисел на два подмножества так, чтобы разница их сумм была минимальной, и найти два подмножества. Если n четное, то размеры должны быть n/2, а если нечетное, то floor[n/2] и ceil[n/2].
Предполагая, что алгоритм DP с псевдополиномиальным временем лучше всего подходит для точного решения, как его можно изменить, чтобы решить эту проблему? И какие алгоритмы приближенного лучше всего подходят для решения этой проблемы?
