在集合中重複數字的子集合算法

我有一個集合S包含自然數和目標t是一個數字。我想知道
我們怎樣才能找到這些數字的總和達到目標t的可能組合數量。
一個數字可以進行任意次數，並且可以採用任何數量的數字來獲得等於目標t的
總和。
在集合中重複數字的子集合算法

Example 
target 6 
Set s {3,8,1,2} 
Solution 3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1 
Total No of solutions possible 7

什麼可以是有效的算法呢？

來源

2012-08-13 abhi

您已經計算出它與[subset sum problem]（http://en.wikipedia.org/wiki/Subset_sum_problem）有關。如果存在x> 0的解決方案，則接受 - 否則拒絕，這更加困難（可減少），然後是減少的子集和問題。所以這個問題也是[NP-Hard]（http://en.wikipedia.org/wiki/NP-hard），在高效（多項式）的標準定義中，沒有已知的*有效的解決方案。你有沒有其他的定義爲你的案件效率？如果是這樣 - 請指定它。 – amit 2012-08-13 07:42:32

@amit爲什麼動態編程不能在這裏工作？ – irrelephant 2012-08-13 07:43:56

@amit我只想知道是否有任何多項式時間解決方案。 – abhi 2012-08-13 07:48:37

如果目標相當小，可以使用動態編程來獲得O（| S | * t）解決方案。以下是Python中的示例代碼：

def combinations(S, t): 
    dp = [1] + [0] * t 
    for i in S: 
     for j in range(0, t - i + 1): 
      dp[j + i] += dp[j] 
    return dp[t]

來源

2012-08-14 06:27:39 devnum

在集合中重複數字的子集合算法

回答

相關問題