由于未排序集数组的形式整数,找到所有可能的子集,其总和大于或等于常数整数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.
动态编程可以帮你算套数有总和> = 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
相关推荐
最新文章