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

Question

给定数组形式的未排序整数集,找到所有可能的子集,其总和大于或等于const整数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

Answer 2

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

不会.问题比@amit(在评论中)提到的更难.找出是否存在与特定k 相加的子集是子集和问题,这是NP难的.相反,你要问有多少解决方案等于一个特定的k,这是一个更加困难的P#类.此外,您的确切问题稍微困难一些,因为您不仅要计算,而且要枚举k和目标<k的所有可能子集.