PartitionProblem variable - фиксированный размер подмножеств

Question

У меня есть проблема, которая является вариацией проблемы раздела, которая является NP-полной. Это проблема оптимизации, а не проблема решения.

Задача: Разбить список чисел на два подмножества так, чтобы их разность сумм была минимальной и находили два подмножества. Если n равно, то размеры должны быть n/2, а если нечетные, то floor[n/2] и ceil[n/2].

Предполагая, что алгоритм ПД псевдополиномиального времени является лучшим для решения , как его можно изменить, чтобы решить эту проблему? И что будет лучшим приблизительно алгоритмов для решения этой проблемы?

Answer 1

Поскольку вы не указали, какой алгоритм использовать я предполагаю, что вы используете один определенный здесь: http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf

Затем с помощью этого алгоритма вы добавляете переменную для отслеживания наилучшего результата, инициализировать его N (сумма всех номеров в списке, так как вы всегда можете взять одно подмножество в качестве пустого набора), и каждый раз, когда вы обновляете T (например: T [i] = true), вы делаете что-то вроде bestRes = abs(i-n/2)<bestRes : abs(i-n/2) : bestRes. И вы возвращаете bestRes. Это, конечно, не меняет сложность алгоритма.

Я не знаю вашего второго вопроса.