给定一组N个整数，列出与金额与GT的所有可能的子集; = K [英] Given a set of n integers, list all possible subsets with sum>=k

问题描述

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

Given an unsorted set of integers in the form of array, find all possible subsets whose sum is greater than or equal to a const integer k, eg:- Our set is {1,2,3} and k=2

可能的子集： -

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

我只能想到一个天真的算法，其中列出了一组所有的子集，并检查是否子集的总和> = K与否，但它的指数算法，并列出所有的子集需要O（2 ^ N）的。我可以用动态规划来解决它在多项式时间？

I can only think of a naive algorithm which lists all the subsets of set and checks if sum of subset is >=k or not, but its an exponential algorithm and listing all subsets requires O(2^N). Can I use dynamic programming to solve it in polynomial time?

推荐答案

列出所有的子集将是仍然 O（2 ^ N），因为在最坏的情况下你可能还是得从空单列出所有的子集分开。

Listing all the subsets is going to be still O(2^N) because in the worst case you may still have to list all subsets apart from the empty one.

动态编程可以帮你算套数有总和＆GT; = K

Dynamic programming can help you count the number of sets that have sum >= K

您去自下而上的跟踪有多少亚群范围 [1..K] 总结出一些价值。这样的方法将是 O（N * K）这将是只用于小型可行 K 。

You go bottom-up keeping track of how many subsets summed to some value from range [1..K]. An approach like this will be O(N*K) which is going to be only feasible for small K.

与动态规划解决方案的想法是最好用一个例子来说明。考虑这种情况。假设你知道你知道所有的第一个组成的套我元素 T1 总和 2 和 T2 总和 3 。比方说，在未来 I + 1 元素是 4 。鉴于所有现有的集合，我们可以建立所有新集通过任何附加元素 I + 1 或离开它。如果我们离开它，我们得到 T1 子集的总和 2 和 T2 子集的总和 3 。如果我们将其追加然后我们得到 T1 子集的总和 6 （2 + 4）和 T2 的总和 7 （3 + 4）。这使我们的子集那笔数目为（2,3,6,7）由第一个 I + 1 元素。我们继续下去，直到 N 。

The idea with the dynamic programming solution is best illustrated with an example. Consider this situation. Assume you know that out of all the sets composed of the first i elements you know that t1 sum to 2 and t2 sum to 3. Let's say that the next i+1 element is 4. Given all the existing sets we can build all the new sets by either appending the element i+1 or leaving it out. If we leave it out we get t1 subsets that sum to 2 and t2 subsets that sum to 3. If we append it then we obtain t1 subsets that sum to 6 (2 + 4) and t2 that sum to 7 (3 + 4). That gives us the numbers of subsets that sum to (2,3,6,7) consisting of the first i+1 elements. We continue until N.

在伪code，这可能是这个样子：

In pseudo-code this could look something like this:

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

这篇关于给定一组N个整数，列出与金额与GT的所有可能的子集; = K的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！