生成總和算法

我必須爲算法構建一個代碼。我必須用我的算法實現如下：生成總和算法

我有三個數字，4,6,8。我必須用這些數字中的兩個產生總和，然後用三個這樣的數字和四個數字等等總和。當然，在這個例子中可以有重複：4 + 4 + 6

我想到了使用「for」循環，因此可以使用兩個嵌套for循環生成其中兩個數字的和。三個嵌套的「for」循環將給出三個數字的總和等...

我可以通過使用「for」約束這個解決方案，例如直到五個數字的總和，但這不是一個通用的解決方案。

有沒有一種方法或算法或數學方法來做到這一點？

這與數學組合有些相似之處。

來源

2014-02-10 Vlad

是的，你可以使用遞歸。將示例輸入與完整的預期輸出結合起來可能也是有幫助的，因此您所要做的完全是100％清晰的。 – Dukeling

如果考慮到x + x + x + ... + x（n次）= x * n，您可以避免遞歸併獲得更高的性能。 –

@ n.m。爲了避免遞歸，你需要做的比這更多，因爲它不會解決5 + 3 = 4 + 4。 – amit

你只需要兩個循環的條款的任何給定數。假設你想要n個值的總和。對於任何給定總和您有n個倍8，N 倍6和n 倍4，其中n + N + N = N。爲了生成所有可能的組合，您只需要循環n 和n ，可以從中計算出n的值。在Python中：

def findsums(n): 
    # n8 = [0..n] 
    for n8 in range(n+1): 
     #n6 = [0..n-n8] 
     for n6 in range(n+1-n8): 
      n4 = n - n8 - n6 
      # build the string consisting of n terms 
      s = "+8" * n8 + "+6" * n6 + "+4" * n4 
      # print, and strip the first '+' character 
      print("{0}={1}".format(s[1:], 8*n8+6*n6+4*n4)) 

findsums(5)

來源

2014-02-10 11:05:45 pentadecagon

您可以從Power set推導出您的解決方案。

不同之處在於你的情況，你可以有重複，並且似乎你有一個子集的最大尺寸。

在互聯網上有很多實現可用。

來源

2014-02-10 10:30:11

雖然對於一般情況正確 - 對輸入有一些限制（元素是相對較小的整數） - 但這可以比生成所有子集和通過利用動態規劃和求和函數的行爲進行求和更有效。 – amit

這是subset sum problem的變體，假設您的元素都是小整數，它可以在僞多項式時間內使用動態編程高效地解決。

f(0,i) = true 
f(x,i) = false if n < 0 
f(x,i) = f(x,i-1) OR f(x-arr[i],i-1)

每個數字x使得f(x,_)=true是一個答案。它可以通過避免遞歸來完成：

table <- int [sum(array)+1][n+1] //2 dimensional table 
init table[x][0]=false for each x!=0 
init table[0][i]=true for each i 
for each x in 1:sum(arr)+1: 
    for each i in 1:n+1: 
     if x-arr[i] >= 0: 
      table[x][i] = table[x][i-1] OR table[x-arr[i]][i-1] 
     else: 
      table[x][i] = table[x][i-1] 
//done generating table, output answers: 
for each x in 1:summ(arr)+1: 
    if (table[x][n] ==true) print x

這個回答假設是沒有限制的子集的大小 - 如果有，它可以通過添加另一個維度表來完成。

運行時間爲O(sum(arr)*n)

來源

2014-02-10 10:50:42 amit

生成總和算法

回答

相關問題