Если задано множество n целых чисел, перечислите все возможные подмножества с sum >= k

Учитывая несортированный набор целых чисел в виде массива, найдите все возможные подмножества, сумма которых больше или равна целому числу const, например: - наш набор {1,2,3} и k = 2

Возможные подмножества: -

 {2},
 {3},
 {1,2},
 {1,3},
 {2,3}, 
 {1,2,3}

Я могу думать только о наивном алгоритме, в котором перечислены все подмножества множества и проверки, если сумма подмножествa >= k или нет, но для его экспоненциального алгоритма и перечисления всех подмножеств требуется O (2 ^ N). Могу ли я использовать динамическое программирование для его решения в полиномиальное время?

Ответ 1

Список всех подмножеств будет оставаться O(2^N), потому что в худшем случае вам все равно придется перечислять все подмножества, кроме пустого.

Динамическое программирование может помочь вам подсчитать количество наборов с sum >= K

Вы идете снизу вверх, отслеживая, сколько подмножеств суммируется с некоторым значением из диапазона [1..K]. Такой подход будет O(N*K), который будет возможен только при малых K.

Идея с решением динамического программирования лучше всего иллюстрируется примером. Рассмотрим эту ситуацию. Предположим, вы знаете, что из всех наборов, состоящих из первых элементов i, которые вы знаете, t1 sum to 2 и t2 sum to 3. Скажем, что следующий элемент i+1 - 4. Учитывая все существующие наборы, мы можем построить все новые наборы путем добавления элемента i+1 или его исключения. Если мы оставим это, получим подмножества t1, которые суммируются с подмножествами 2 и t2, которые суммируются с 3. Если мы добавим его, мы получим подмножества t1, которые суммируются с 6 (2 + 4) и t2, которые суммируются с 7 (3 + 4). Это дает нам числа подмножеств, которые суммируются с (2,3,6,7), состоящим из первых элементов i+1. Мы продолжаем до N.

В псевдокоде это может выглядеть примерно так:

int DP[N][K];
int set[N];

//go through all elements in the set by index
for i in range[0..N-1]
   //count the one element subset consisting only of set[i]
   DP[i][set[i]] = 1

   if (i == 0) continue;

   //case 1. build and count all subsets that don't contain element set[i]
   for k in range[1..K-1]
       DP[i][k] += DP[i-1][k]

    //case 2. build and count subsets that contain element set[i]
    for k in range[0..K-1] 
       if k + set[i] >= K then break inner loop                     
       DP[i][k+set[i]] += DP[i-1][k]

//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1

Ответ 2

Могу ли я использовать динамическое программирование для его решения в полиномиальное время?

Нет. Проблема еще сложнее, чем @amit (в комментариях). Поиск того, существует ли подмножество, суммируемое с конкретным k, это проблема подмножества сумм, которая NP-hard. Вместо этого вы просите, сколько решений равно конкретному k, что находится в гораздо более сложном классе P #. Кроме того, ваша точная проблема немного сложнее, поскольку вы хотите не только подсчитывать, но и перечислять все возможные подмножества для k и целей < к.

Ответ 3

Если k равно 0, и каждый элемент множества положителен, то у вас нет выбора, кроме как выводить все возможные подмножества, поэтому нижняя граница этой проблемы равна O (2 ^N) - - время, затрачиваемое на выпуск выходного сигнала.

Если вы ничего не знаете о значении k, о котором вы нам не сказали, не существует более простого общего решения, позволяющего просто проверять каждое подмножество.