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

Question

给定数组形式的一组未排序的整数，找到所有可能的子集，其总和大于或等于一个常量整数 k，例如:- 我们的集合是 {1,2,3} 并且 k=2

可能的子集:-

 {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 .

动态规划解决方案的想法最好用一个例子来说明。考虑这种情况。假设你知道在由第一个 i 组成的所有集合中你知道的元素 t1总和为 2和 t2总和为 3 .假设下一个 i+1元素是 4 .给定所有现有集合，我们可以通过附加元素 i+1 来构建所有新集合。或将其排除在外。如果我们忽略它，我们会得到 t1总和为 2 的子集和 t2总和为 3 的子集.如果我们追加它，那么我们将获得 t1总和为 6 的子集(2 + 4) 和 t2总和为 7 (3 + 4) 和一个仅包含 i+1 的子集总和为 4。这给了我们总和为 (2,3,4,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