Обзор алгоритмов решения задачи о нахождении суммы элементов подмножества

Задача о сумме формулируется следующим образом: найти подмножество Y таких чисел из данной конечной совокупности X , которые в сумме дают заданное число s . Классически задача формулируется в терминах целых чисел [4].

Эквивалентными задачами являются задачи, в которых число s равно 0, или, например, половине суммы всех элементов множества [5, с. 3]. Иногда требуется найти подмножество Y ⊂ X , сумма элементов которого принимает максимально возможное значение, не превосходящее s .

Задача о сумме относится к NP-полным задачам. В теории алгоритмов задачи класса P - это вычислительные задачи, которые можно решить за полиномиальное время. Алгоритмы, трудоемкость которых не ограничена полиномом от длины входа, называются экспоненциальными. Класс NP -это множество задач, у которых проверка правильности результата может быть вы- полнена за полиномиальное время. В теории NP-полноты рассматриваются только задачи разрешения - задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Например, с задачей поиска суммы элементов подмножества Y связана задача разрешения: может ли быть представлено число s в виде суммы каких-либо элементов массива X. Если какой-то алгоритм дал результат – массив Y, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка ^ yi = s требует не более О(n) операций. NP-полная задача -задача из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время [6].

Вычислительная сложность задачи о сумме подмножеств зависит от двух параметров: n и p , где n– число элементов множества, p – число двоичных разрядов в числах, составляющих множество. Если n – мало, то для решения задачи о сумме элементов подмножеств используются методы перебора; если относительно мало p , то используются методы динамического программирования [5, с. 3].

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

Рассмотрим некоторые алгоритмы решения задачи за время, которое экспоненциально зависит от n .

Алгоритмы с экспоненциальной сложностью

Алгоритм 1

Наиболее простой алгоритм заключается в генерации всех подмножеств множества X . Количество всех подмножеств множества из n элементов с учетом пустого подмножества равно 2 ⁿ . Для каждого из этих подмножеств вычисляется сумма элементов и проверяется, равна ли она искомой сумме s . Задача генерации всех подмножеств множества эквивалентна задаче генерации всех n -мерных векторов из нулей и единиц. Если на i- й позиции вектора стоит 1 (единица), это означает, что элемент включен в данное подмножество и должен учитываться при подсчете суммы элементов подмножества. Таким образом, каждому подмножеству соответствует двоичное число или структура, которая имитирует двоичное число. Определение номеров позиций, на которых стоят единицы, позволяет однозначно выделить элементы X и вычислить их сумму.

Можно организовать перебор подмножеств в порядке минимального изменения двоичного кода, т.е. каждое следующее подмножество получается из предыдущего удалением или добавлением ровно одного элемента. Эту задачу решают коды Грея, например: 000, 001, 011, 010, 110, 111, 101, 100.

Это позволяет при вычислении очередной суммы чисел подмножества использовать сумму элементов предыдущего подмножества, вычитая или добавляя соответствующие элементы X .

Следующий алгоритм приведен в [2]. Для формирования сумм подмножеств исходного множества используется операция L = L U ( L + x ).

Первоначально список L содержит нулевой элемент. К каждому элементу текущего списка L добавляется текущий элемент x_i , два списка объединяются в один список L . Например, для i = 1 список L равен {0} U { x 1 }={0, x 1 }. Далее объединяются списки {0, x 1 } и {0 + x 2 , x 1 + x 2 }: L ={0, X i } U { x 2 , X + x 2 }={0, X i , x 2 , X + x 2 } и т.д. Для определения элементов, которые входят в подмножество с заданной суммой, требуется дополнительная память.

Алгоритм 2

• 1.    Создать список L , первоначально состоящий из одного элемента, равного нулю.

• 2.    Для i от 1 до n :

• 3.    Отсортировать элементы из списка L в порядке возрастания.

• 4.    Удалить из списка L все элементы, большие s .

• 5.    Последний элемент из списка L является решением задачи.

Записать в конец списка L элементы, полученные из списка L путем увеличения каждого его элемента на величину x_i .

Пример 1:

Дан массив X = {4, 3, 7.5, 8, 6}, s=13.8, n = 5, тогда:

• 1.    L = {0};

• 2.    i = 1, x 1 = 4, L = L U ( L + x 1 )= {0, 4} ;

• 2.    i = 2, x 2 = 3, L = L U ( L + x₂ )= {0,4, 3, 7};

• 2.    i = 3, x 3 = 7.5, L = L U ( L + x 3 )= {0,4, 3,7,

• 7.5, 11.5, 10.5, 14.5} ;

• 2.    i = 4, x₄ = 8, L = L U ( L+x 4 ) = {0, 4, 3, 7, 7.5, 11.5, 10.5, 14.5, 8, 12, 11, 15, 15.5, 19.5, 18.5, 22.5} ;

• 2.    i = 5, x 5 = 6, L = L U ( L+x ₅) = {0, 4, 3, 7, 7.5, 11.5, 10.5, 14.5, 8, 12, 11, 15, 15.5, 19.5, 18.5, 22.5, 6, 10, 9, 13, 13.5, 17.5, 16.5, 20.5, 14, 18, 17, 21, 21.5, 24.5, 28,5} ;

• 3.    L = {0, 3, 4, 6, 7, 7.5, 8, 9, 10, 10.5, 11, 11.5, 12, 13, 13.5, 14, 14.5, 15, 15.5, 16.5, 17, 17.5, 18, 18.5, 19.5, 20.5, 21, 21.5, 22.5, 24.5, 25.5, 28.5};

• 4.    L = {0, 3, 4, 6, 7, 7.5, 8, 9, 10, 10.5, 11, 11.5, 12, 13, 13.5}

• 5.    s ’ = 13.5

За искомую сумму s’ принимается сумма, максимально приближенная к заданной, s ’ = 13.5.

Оценка сложности алгоритма 2 в худшем случае O ( n 2 ⁿ ) .

Следующий алгоритм 3 содержит аналогичные действия, но имеет иной порядок обработки списков [2, с. 1182-1185]. Сортировка и удаление элементов, превышающих искомую сумму, применяется на каждом шаге. Объединение списков L - L U ( L + x ) производится с одновременной сортировкой элементов по возрастанию. Оба списка L и L + x по построению уже упорядочены, поэтому в процессе объединения этих списков (массивов при программировании) выполняется операция слияния, которая упорядочивает элементы в результирующем списке (алгоритм сортировки слиянием).

Алгоритм 3

• 1.    Создать список L , первоначально состоящий из одного элемента, равного нулю.

• 2.    Для от 1 до n :

  • 2.1.    Записать во вспомогательный список T элементы, полученные из списка L путем увеличения каждого его элемента на величину x .

  • 2.2.    Объединить списки L и T , выполняя сортировку слиянием.

  • 2.3.    Отсортированный список записать в L .

  • 2.4.    Удалить из списка L все элементы, большие s.

  • 2.5.    Исключить повторяющиеся значения в новом списке.

• 3.    Последний элемент из списка L является решением задачи.

Поскольку длина списка L может достигать значения 2 ⁿ , в общем случае время выполнения алгоритма ведет себя как показательная функция [2, с. 1182].

Оценка сложности алгоритма 2 в худшем случае O ( n 2 ⁿ ) .

Лучший экспоненциальный алгоритм имеет время выполнения O (2 ^{n /2}) и опубликован в [7] авторами E. Horowitz и S. Sahni.

Алгоритм 4

• 1.    Исходное множество x из n элементов

• 2.    Для x 1 - x [1: l ] и x 2 - x [ n - 1 + 1:n ] формируются списки L ₁ и L ₂ сумм элементов всех подмножеств, которые можно образовать из x 1 и x 2 . Списки сортируются.

• 3.    Выполняется сравнение сумм элементов этих списков с искомым значением s . Список L ₁ просматривается в порядке убывания, начиная с наибольшего элемента, а L ₂ - в порядке возрастания, начиная с наименьшего элемента. Если сумма текущих элементов больше s , происходит переход к следующему элементу в L ₁ , а если меньше s , то переход осуществляется к следующему элементу в L ₂ . Если сумма равна s , то подмножество с заданной суммой найдено. Если при переборе достигнута граница, нижняя в L ₁ или верхняя в L ₂ , а сумма не равна s , то исходная задача не имеет решения.

n делится на два подмножества по l - — эле- ментов. Если число n - нечетное, то каждое

, 1 ( n + 1) подмножество будет содержать ^{1 -} —2— элементов: x 1 = x [1: l ] и x ₂ = x [ n - l + 1: n ].

В пункте 2 список из сумм элементов всех подмножеств L ( L ₁ или L ₂ ) также формируется на основе операции L - L U ( L + x ) с сортировкой слиянием.

Переборные алгоритмы 1-4 имеют экспоненциальную сложность и могут быстро работать только при относительно небольших значениях n . С ростом n длина списка L быстро растет, и задача становится практически неразрешимой за разумное время выполнения.

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

Идея следующего алгоритма [2, с. 11821183] ^аёёр ^aadny а ПТ ёбаи ai ёё ni ёпёаL на каждом шаге его создания. Если два значе- ния a и b в списке L мало отличаются друг от друга, то элемент b можно исключить из

L , если выполняется условие (1):

b

1 + 5

< a <  b

где 5 , 0< 5 <1 - параметр сокращения списка.

В полученном после сокращения списке L’ для каждого удаленного элемента b из списка L будет содержаться элемент a из L’ , который будет являться аппроксимацией удаленного. На каждом шаге список сортируется по возрастанию, и кандидат b на сокращение не меньше последнего элемента текущего списка. Поэтому достаточно выполнить проверку 2:

b <  a (1 + 5 )                      (2)

где b - текущий анализируемый элемент xi , a - последний элемент текущего списка.

Если условие (2) выполняется, то b ( b = x_i ) в список не добавляется, иначе x _i добавляется в конец списка.

Алгоритм сжатия списка

На каждой итерации список L предварительно сортируется. Текущий элемент добавляется в новый список L в двух случаях:

• 1)    элемент является первым элементом списка L;

• 2)    элемент нельзя аппроксимировать последним из текущего списка [2, с. 1182].

В остальных случаях элементы удаляются.

Пример 2. Пусть L ={4, 4.2, 6, 7, 14, 15, 15.2, 20, 23}, 5 = 0.1.

Список после сокращения: {4, 6, 7, 14, 20, 23} (см. табл. 1).

Алгоритм 5

• 1.    Создать список L , первоначально состоящий из одного элемента, равного нулю.

• 2.    Для i от 1 до n :

  • 2.1.    Записать во вспомогательный список T элементы, полученные из списка L путем увеличения каждого его элемента на величину x_i .

  • 2.2.    Объединить списки L и T , выполняя сортировку слиянием.

• 2.3.    Отсортированный список записать в L .

• 2.4.    Выполнить процедуру сокращения элементов списка L .

• 2.5.    Удалить из списка L все элементы, большие s .

• 3.    Максимальный элемент из списка L является решением задачи.

Таблица 1

Список и анализируемый элемент	Анализ текущего числа в списке	Действие
{4}, x 2 =4.2	4.2<4(1+0.1)=4.4	Элемент «4.2» удаляется из списка
{4}, x 3 =6	6>4(1+0.1)=4.4	В список добавляется элемент «6»
{4, 6}, x 4 =7	7>6(1+0.1)=6.6	В список добавляется элемент «7»
{4, 6, 7}, x 5 =14	14>7(1+0.1)=7.7	В список добавляется элемент «14»
{4, 6, 7, 14}, x 6 =15	15<14(1+0.1)=15.4	Элемент «15» удаляется из списка
{4, 6, 7, 14}, x 7 =15.2	15.2<14(1+0.1)=15.4	Элемент «15.2» удаляется из списка
{4, 6, 7, 14}, x 8 =20	20>14(1+0.1)=15.4	В список добавляется элемент «20»
{4, 6, 7, 14, 20}, x 9 =23	23>20(1+0.1)=22	В список добавляется элемент «23»

Сжатие входного списка

Представленный алгоритм имеет полиномиальное время выполнения [2, с. 11821186].

В алгоритмах 1-5 информация об элементах, входящих в подмножества, также может храниться в виде двоичных чисел.

В [3] предложен другой подход к решению задачи на основе метода динамического программирования.

Пусть задана пара ( X , s ) , где X = { x 1 , x 2 , ... x n } представляет собой множество положительных целых чисел, s — положительное целое число, n - количество элементов множества X. Требуется отыскать среди подмножеств множества X такое, сумма элементов которого была бы ближе всего к s , но не превосходила его. Для решения задачи вводится функция T ( i , j ) , значения которой определяют элементы таблицы T. Строка таблицы с номером i содержит суммы элементов подмножеств, образованных из первых i элементов X . Каждый элемент столбца с номером j , где изменяется от 0 до s , содержит максимальную сумму, не превышающую j , которую можно составить из первых i элементов X . Суммы элементов подмножеств X , превосходящие s , не рассматриваются.

Таблица заполняется слева направо и сверху вниз. Заполнение элемента таблицы с номером (i, j) происходит по следующим правилам. Если текущий элемент xi превышает сумму j , то он в набор не включается, и элемент матрицы T(i, j) приравнивается к элементу того же столбца предыдущей строки T(i -1, j). Если текущий элемент xi меньше j , то его можно попытаться включить в набор с целью получить максимальную сумму, не превосходящую j . Для этого необходимо сравнить два числа. Пер- вое число образовано суммой T(i -1, j - xt) + xi, а второе T(г -1, j). Ячейка T(i -1, j - xi) с номером столбца j - xi содержит максимальную сумму, не превышающую j - xi, которую можно составить из первых i -1 элементов X. Выбираем максимальное из чисел T(i -1, j - xi) + xi и T(i -1, j) [1, c. 24-25]. Построение таблицы завершается заполнением последнего столбца с номером j = 5 . Искомая сумма, если она достижима, всегда хранится в последней ячейке таблицы.

Алгоритмы, которые приведены далее, используют приведенные правила заполнения таблицы, но отличаются способом хранения информации о суммах подмножеств.

Первый из приведенных ниже алгоритмов работает с таблицей двоичных значений.

Для начала работы алгоритма нужно определить начальные значения Т (0 , j ) и Т ( i, 0). При пустом множестве X нельзя набрать сумму j >0, следовательно, Т (0 , j ) = 0. При любом множестве X можно набрать нулевую сумму, не задействовав элементы, следовательно, Т ( i, 0) = 1.

Алгоритм 6

• 1.    Задать начальные значения функции T :

• 2.    Заполнить таблицу, используя рекуррентное соотношение при i >  1 и j >  1:

T (0, j ) = 0 при j >  1;

T ( i ,0) = 1 при i >  1;

T (0,0) = 1.

Для j =1 до s :

Для i =1 до n :

T(i, j) = T(i-1, j),j < x

T(i, jI = max(T(i -1, j),T(i -1, j - x)),j > x Пример 3:

X ={3, 7, 4, 5, 2, 6}, n =6, s =12 (см. табл. 2).

Задаче, где n =6, s =12, соответствует ячейка таблицы T (6,12) = 1 , следовательно, решение данной задачи существует. Для определения списка элементов, входящих в сумму, рассматриваются ячейки T (6,12), T (5,12) и Т(4,12). Значения данных ячеек равны, значит, сумму s =12 можно набрать без элементов x₆ и x₅ . В ячейке Т(3,12) стоит нулевое значение , значит, элемент x₄ должен быть

Таблица 2

Выходная таблица

x i	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
	0	1	0	0	0	0	0	0	0	0	0	0	0	0
3	1	1	0	0	1	0	0	0	0	0	0	0	0	0
7	2	1	0	0	1	0	0	0	1	0	0	1	0	0
4	3	1	0	0	1	1	0	0	1	0	0	1	1	0
5	4	1	0	0	1	1	1	0	1	1	1	1	1	1
2	5	1	0	1	1	1	1	1	1	1	1	1	1	1
6	6	1	0	1	1	1	1	1	1	1	1	1	1	1

Таблица 3

Выходная таблица

xi i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 0 0 0 3 3 3 3 3 3 3 3 3 3 7 2 0 0 0 3 3 3 3 7 7 7 10 10 10 4 3 0 0 0 3 4 4 4 7 7 7 10 11 11 5 4 0 0 0 3 4 5 5 7 8 9 10 11 12 2 5 0 0 2 3 4 5 6 7 8 9 10 11 12 6 6 0 0 2 3 4 5 6 7 8 9 10 11 12 включен в искомое подмножество.

Суммарное значение оставшихся элементов набора равно s-x₄=12-5=7 . Просматриваем столбец с индексом «7». Так как T (4,7) = 1 , сумму, равную 7, набрать можно. В столбце «7» ищем ячейку, в которой находится первая единица этого столбца. Индекс этой строки равен 2, значит, элемент x₂ входит в подмножество.

Оставшаяся требуемая сумма элементов подмножества равна s’-x₂=7-7=0, следовательно, искомая сумма набрана. Искомое подмножество Y ={5, 7} [1, c. 17-19].

Достоинством алгоритма 6 является возможность работать с таблицей двоичных значений.

Можно хранить в таблице значения сумм. И тогда модификацией алгоритма 6 является алгоритм 7.

Алгоритм 7

• 1.    Задать начальные значения функции T . При пустом множестве X нельзя набрать сумму j >0. При любом множестве X можно

• 2.    Заполнить таблицу, используя рекуррентное соотношение при i >  1 и j >  1:

набрать нулевую сумму, не задействовав элементы, следовательно:

T (0, j ) = 0при j >  1;

T ( i , 0) = 0 при i >  1.

T (0,0) = 0

Для j =1 до s :

Для i =1 до n :

если j <  x i

T (i, j) = T (i-1, j)

иначе

T(i,j)=max(T(i - 1,j),T(i - 1,j - xi)+xi)

Пример 4:

X = { 3, 7, 4, 5, 2, 6 } , n = 6, 5 = 12 (см. табл. 3).

По таблице легко восстановить элементы множества X , которые образуют искомую сумму.

Так как T(6,12) = 12, искомая сумма 5 = 12 набирается. Анализ таблицы проводится аналогично предыдущему случаю: в искомое подмножество должны быть включены элементы x4 = 5 и x2 = 7.

Следующий алгоритм является модификацией алгоритма 7. Отличие состоит в том, что если в столбце j в какой-то строке i зафиксирован тот факт, что сумму j набрать можно, – содержимое нижних строчек этого столбца повторяет T ( i , j ) . Элементы выше строчки i равны 0, что означает невозможность точно набрать сумму j , используя предыдущие элементы.

Алгоритм 8

• 1.    Задать начальные значения функции T :

• 2.    Заполнить таблицу, используя рекуррентное соотношение при i >  1 и j >  1.

T (0, j ) = 0 при j >  1;

T ( i ,0) = 0 при i > 1.

T (0,0) = 0

Для j =1 до s :

Для i =1 до n :

если j < xi , то T(i,j) = T(i -1, j);если j == xi , то T(i, j) = j;

если j >  x i

если T(i -1, j) < T(i -1, j - xi), то T (i, j) = j;

иначе T ( i , j ) = T ( i - 1, j ).

Приведенный текст алгоритма отражает логику расчета элементов таблицы. Сэкономить время заполнения таблицы можно, если зафиксировать в строчке i факт, что сумму j набрать можно, оставшиеся элементы заполнить значением j . Начальные значения всех элементов таблицы нулевые.

Пример 5:

X = { 3, 7, 4, 5, 2, 6 } , n = 6, 5 = 12

(см. табл. 4).

Данный алгоритм удобен тем, что здесь проще, чем в предыдущих алгоритмах 6-8, определяются элементы, составляющие искомую сумму.

Восстановление элементов суммы происходит аналогично предыдущему примеру.

Временная сложность «табличных» алгоритмов растет линейно по n и s , составляет O ( ns ) операций, но приведенные алгоритмы позволяют получить точное решение. Если s велико, то для уменьшения времени вычисления можно все числа поделить на константу, например, 10, округлить, отбросить повторяющиеся значения и получить приближенный алгоритм.

В заключение отметим, что выбор того или иного алгоритма определяется поставленной задачей, ресурсами, которыми располагает пользователь, а также требуемой точностью вычисления суммы элементов подмножества.

Таблица 4

Выходная таблица

x i	i \ j	0	1	2	3	4	5	6	7	8	9	10	11	12
	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	1	0	0	0	3	0	0	0	0	0	0	0	0	0
7	2	0	0	0	3	0	0	0	7	0	0	10	0	0
4	3	0	0	0	3	4	0	0	7	0	0	10	11	0
5	4	0	0	0	3	4	5	0	7	8	9	10	11	12
2	5	0	0	2	3	4	5	6	7	8	9	10	11	12
6	6	0	0	2	3	4	5	6	7	8	9	10	11	12