Вы должны найти проблему с суммой подмножеств. В вашем случае вы пытаетесь получить сумму подмножества S/2, где S - полная сумма набора. Для этого в случае целых чисел существует простой алгоритм динамического программирования, наиболее известный. К сожалению, это псевдополиномиальное время. Это означает, что время выполнения зависит от размера элементов. Это делает время экспоненциальным в обычном смысле, но оно прекрасно работает, если элементы не слишком велики.
Динамическая программа суммирования подмножеств нуждается в небольшой модификации, чтобы обеспечить выполнение требования ровно для N элементов e[i]. Пусть Q(i, s, n) истинно тогда и только тогда, когда существует подмножество, состоящее из элементов, выбранных от 1 до i, суммирующихся с s и содержащих ровно n‹=i элементов.
затем
Q(i, s, n) = Q(i - 1, s, n) or Q(i - 1, s - e[i], n - 1)
В базовом случае говорится, что при полном отсутствии элементов сумма и требуемое число в подмножестве должны быть равны нулю, иначе Q ложно:
Q(0, 0, 0) = истина, иначе Q(0, _, _) ложно.
Чтобы получить ответ, вычислите таблицу DP для Q(2N, k, N), k = потолок (S/2), потолок (S/2)-1, ..., пока не найдете истинное значение.
Обратите внимание, что эта задача достаточно близка к сумме подмножеств, чтобы сделать ее NP-сложной. Это означает, что настоящий алгоритм полиномиального времени (например, ваше предложение по сортировке) будет приближением к оптимальности. Конечно, это вполне может подойти для реальных целей.
person
Gene
schedule
12.09.2012
