子集总和：查找总和大于K的子集 [英] Subset Sum : Find subset whose sum greater than K

问题描述

我有一个正整数数组，比如{a1，a2，....，an}，我想找出满足以下条件的所有可能的子集：

I have an array of positive integers say {a1, a2, ...., an}, and I want to find out all possible subsets of the array which satisfy the following condition:

(sum >= K)

其中K是一个正整数。我知道此问题的解决方案是动态编程，但无法考虑如何在这种情况下使用它。请帮忙。

where K is a positive integer. I know the solution for this problem is dynamic programming, but unable to think how to use it for this case. Please help.

P.S。 ：我并不需要所有的子集，而是说形成的所有子集的所有元素的乘积。

P.S. : I don't exactly need all the subsets, but say product of all elements for all subsets formed.

推荐答案

您的问题看起来类似于0-1背包问题，除了在事物上-通常这种限制是，总和必须小于K 。

Your problem looks similar to 0-1 Knapsack problem, except on thing - usually this restriction is, that sum must be smaller than K.

但是您列出了问题是，限制在哪里，金额必须更大。

But you list the problem, where restriction is, that sum must be bigger.

因此，例如，如果找到子集，其总和大于K，则可以添加集合中任何不包含在子集中的元素，并且仍然是答案。假设您的集合是{a1，a2，a3，a4} ans sum {a1}> =K。然后，您有2 ^ 3种方式将a2，a3和a4添加到子集中。

So, for example, if you find subset, sum of it is bigger than K, then you could add any element of set, that not included in your subset and this is still the answer. Let's assume, your set is {a1, a2, a3, a4} ans sum {a1} >= K. Then, you have 2^3 ways to add a2, a3 and a4 to your subset.

因此，此问题看起来像指数问题，因为您需要列出所有可能的变体。

So, this problem looks like exponential problem, since you need to list all possible variations.

最坏的情况是，当K = 0时，并且您有N个元素大于0。因此，您需要列出2 ^ N个子集。

Worst case is, when K = 0. And you have N elements greater than 0. So, you need to list 2 ^ N subsets.

可能，此链接可以帮助 http://en.wikipedia.org/wiki/Subset_sum_problem

Probably, this link could help http://en.wikipedia.org/wiki/Subset_sum_problem

这篇关于子集总和：查找总和大于K的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！