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

小编典典

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

algorithm

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

可能的子集：

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

我只能想到一个天真的算法，该算法列出了集合的所有子集，并检查子集的总和是否> = k，但是它是指数算法并列出所有子集需要O（2 ^
N）。我可以使用动态编程在多项式时间内求解吗？

阅读 359

2020-07-28

共1个答案

小编典典

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

动态编程可以帮助您计算具有sum >= K

您可以自下而上地跟踪有多少子集总计为range的某个值[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

2020-07-28