Интересная вариация к проблеме сумм подмножеств

Question

Интересный вариант задачи о сумме подмножеств был представлен мне другом из работы:

При заданном наборе S натуральных чисел размера n и целых чисел a и K есть подмножество R(из множества S), который содержит точно элементы , чья сумма равна K?

Он утверждает, что это можно сделать с временной сложностью O (nka), я не смогпридумать алгоритм динамического программирования, который достиг этого времени выполнения.Можно ли это сделать?

Answer 1

Пусть S = {s1, \ ldots, sn}

Пусть P (j, K, a) истинно, если в s1, \ ldots, sj можно найти элементы с суммой до K.

Тогда P (j, K, a) = P (j-1, K-sj, a-1) ИЛИ P (j, K, a) (либо sj необходим, либо не нужен).

Затем алгоритм состоит из заполнения трехмерной таблицы размерности n на K + 1 на a + 1. Каждая запись занимает постоянное время для заполнения, следовательно, сложность времени (и пространства) составляет O (нКа)

Answer 2

Это можно сделать, если k и a достаточно малы, так что мы можем объявить массив

bool found[a][k]

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

Скажем, для индексов a = 1 и k = 7, а текущее значение из S равно 7,

, если найдено [1][7] верно, тогда вы также можете быть уверены, что found [2] [14] также верно.

Когда итерация заканчивается, все, что вам нужно сделать, это проверить, что [a] [k]правда или нет.