給定的整數集合的子集，其和爲常數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

回答

相關問題