13

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

可能的子集：-

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

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

4

3 回答 3

11

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

动态规划可以帮助您计算具有sum >= K

您自下而上跟踪有多少子集总和为 range 中的某个值[1..K]。像这样的方法将O(N*K)只适用于小型K.

动态规划解决方案的想法最好用一个例子来说明。考虑这种情况。假设您知道在由第一个i元素组成的所有集合中，您知道t1sum to2和t2sum to 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
于 2013-08-06T17:56:30.553 回答
6

我可以使用动态规划在多项式时间内解决它吗？

不，这个问题比@amit（在评论中）提到的还要难。查找是否存在总和为特定 k 的子集是子集和问题，这是 NP-hard。相反，您要询问有多少解决方案等于特定的 k，这是P#更困难的类别。此外，您的确切问题稍微困难一些，因为您不仅要计数，还要枚举 k 和目标 < k 的所有可能子集。

于 2013-08-06T17:17:32.950 回答
1

如果 k 为 0，并且集合的每个元素都是正数，那么您别无选择，只能输出每个可能的子集，所以这个问题的下限是 O(2 N )——产生输出所用的时间。

除非您对未告诉我们的值 k 有更多了解，否则没有更快的通用解决方案来检查每个子集。

于 2013-08-06T17:20:53.507 回答