给定的整数集合的子集，其和为常数N：Java

给定一组整数，如何找到一个与给定值相加的子集......子集问题？给定的整数集合的子集，其和为常数N：Java

示例：S = {1,2,4,3,2,5}并且n = 7 找出总和为n的可能子集。我试图谷歌找到很多链接，但不清楚。我们如何在java中解决这个问题，以及使用哪种数据结构及其复杂性？

来源

2011-06-06 crackerplace

作业问题？ – 2011-06-06 11:04:44

您似乎有一个Integer列表，因为您有重复项。即2次。 – 2011-06-06 11:05:23

它**是NP-complete [子集总和问题]（http://en.wikipedia.org/wiki/Subset_sum_problem）（我们应该要求谷歌重新编写维基百科...） – 2011-06-06 11:11:29

我不会给你任何代码，但解释它是如何工作的。

运行从0 to (2^k-1)
在其二进制表示一个循环对于每个值在图1中，1表示该值被选择，否则为0。
测试以查看所选号码的总和是否等于n。

上述方法将评估给定集合的每个可能子集。

如果数值的上限很小，那么可以使用动态规划方法。

来源

2011-06-06 11:08:23

@Gunner ..男人你发射的确切苏..清澈.. ..什么谷c帮助.. – crackerplace 2011-06-06 11:34:39

@Gunner现在我认为的复杂性是O（2^n）...我们有任何其他方式来解决它？ – crackerplace 2011-06-06 12:32:14

是的，这个的复杂性是2^n。还有一个O（k * n）方法，其中n是元素的总数和k个元素。它增加了使用O（n）额外内存的缺陷。这个想法是跟踪到目前为止使用的元素，比如说j，然后如果你添加一个[j + 1]，那么每个元素都可以知道你可以使用元素达到[j + 1 ] 等等。 – 2011-06-06 12:47:47

在三个步骤：

找到S的幂（集合S的所有子集）
计算每个子集的总和
过滤掉没有子集总和为7.

来源

2011-06-06 11:13:42 adamse

以编程方式如何找到功率设置..这就是问题btw？ – crackerplace 2011-06-06 11:30:29

给定的整数集合的子集，其和为常数N：Java

回答

相关问题