查找具有給定總和的排序數組的子集的最有效算法

因此，我一直在閱讀帖子，如Finding three elements in an array whose sum is closest to a given number和Find a pair of elements from an array whose sum equals a given number，並且似乎幾乎所有問題都針對成對或三元組。查找具有給定總和的排序數組的子集的最有效算法

我的問題是，給定一個排序數組，一些ñ，以及和小號，有一個「通用」算法，通過檢查，並在陣列中添加ň號返回小號？我現在知道如何高效地進行配對和三聯體操作，但我似乎無法找到任何與有關的算法n> 3

來源

2014-09-20 user3277633

http://en.wikipedia.org/wiki/Subset_sum_problem – 2014-09-20 16:50:01

您的問題的標題是誤導。「X數的總和」當然可以在O（X）時間內計算。 – 2014-09-20 18:02:23

對不起，我不完全確定如何工作。有什麼建議麼？ – user3277633 2014-09-20 18:41:33

設MAX爲數組大小。考慮所有MAX數字的二進制數字;讓數字j的「1」表示「第j個數字包含在總和S中」，而數字j的0表示它不是。

然後有2^MAX可能的解決方案。你可以做一個線性搜索。效率不高。

可以代替修剪做到這一點：

findSolution (Array, MAX, n, S, SolutionSoFar, j) is 
    if SolutionSoFar has n digits set to 1 
    if the sum it represents == S 
     return SolutionSoFar -- we win 
    else 
     return false 

    if (result = findSolution (Array, MAX, n, S, SolutionSoFar with jth set to 1, j+1)) 
    return result 
    else if (result = findSolution (Array, MAX, n, S, SolutionSoFar with jth set to 0, j+1)) 
    return result 
    else 
    return false 


findSolution (Array, MAX, n, S, a binary number of MAX digits all 0's, 0)

O型符號仍然會顯示這是指數，但它是更好的。

您現在可以將更多的智能放在這裏：拋出一個項目> S-（n-1）（假定所有項目的大小至少爲1）的解決方案。傾向於添加接近（S-（到目前爲止））/（剩下要添加的項目）的平均值的東西。

如果存在比指數更好的算法，或者我們可以證明沒有，那麼就不得不進一步思考。

來源

2014-11-17 19:55:47

查找具有給定總和的排序數組的子集的最有效算法

回答

相關問題