给定一组n个整数，列出sum>=k的所有可能子集

Question

可能的子集：-

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

我只能想到一个朴素的算法，它列出集合的所有子集，并检查子集和是否>=k，但它是一个指数算法，列出所有子集需要O(2^n)。我能用动态规划在多项式时间内求解吗？

Answer 1

列出所有子集仍然是O(2^n)，因为在最坏的情况下，您可能仍然必须列出除空子集之外的所有子集。

动态编程可以帮助您计算具有sum>=k的集合的数量

您可以自下而上跟踪从[1..k]范围中有多少子集相加到某个值。类似这样的方法将是O(n*k)，它将只对小的k可行。

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