如何找到所有匹配的數字，在給定的數組中的總和爲'N'

我的目標是找到所有可能的總和的總和。例如，如果陣列是 2 59 3 43 5 9 8 62 10 4，如果總爲12，則可能的組合是如何找到所有匹配的數字，在給定的數組中的總和爲'N'

這裏是第一組碼，即我已經寫。想知道在這方面可以做的最好的改進。

int find_numbers_matching_sum(int *number_coll, int total) 
{ 

    int *search_till = lower_bound(number_coll,number_coll+TOTAL_SIZE, total); 
    int location = search_till - number_coll; 
    if (*search_till > total && location > 0) 
    { 
     --location; 
    } 

    while (location >= 0) 
    { 
     find_totals(number_coll,total,location); 
     --location; 
    } 
    return 1; 
} 

int find_totals(int *number_coll, int total, int end_location) 
{ 
    int left_ones = total - number_coll[end_location]; 
    int curloc = end_location; 
    int *search_till = 0; 
    int location ; 
    int all_numbers[10]; 
    int i = 0; 

    all_numbers[i] = number_coll[end_location]; 
    while (left_ones && curloc >= 0) 
    { 
     search_till = lower_bound(number_coll,number_coll+end_location, left_ones); 
     location = search_till - number_coll; 
     if (*search_till > left_ones && location > 0) 
     { 
      --location; 
     } 
     else if (left_ones < *search_till) 
     { 
      break; 
     } 
     curloc=location; 
     left_ones = left_ones - number_coll[curloc]; 
     all_numbers[++i] = number_coll[curloc]; 
     end_location = curloc - 1; 
    } 

    if (!left_ones) 
    { 
     while (i>=0) 
     { 
      cout << all_numbers[i--] << ' '; 
     } 
    } 
    cout << endl; 
    return 1; 


}

來源

2010-07-21 user373215

使用'lower_bound（）'你似乎假設集合是有序的？負數是否允許？ – 2010-07-21 19:07:45

在此解決方案中，我正在對數字進行排序，然後調用該函數。但有沒有更好的方法？ – user373215 2010-07-21 19:12:36

http：// stackoverflow的可能重複。com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number – 2010-07-21 20:48:35

#include <iostream> 
#include <vector> 

using namespace std; 

struct State { 
    int v; 
    const State *rest; 
    void dump() const { 
     if(rest) { 
      cout << ' ' << v; 
      rest->dump(); 
     } else { 
      cout << endl; 
     } 
    } 
    State() : v(0), rest(0) {} 
    State(int _v, const State &_rest) : v(_v), rest(&_rest) {} 
}; 

void ss(int *ip, int *end, int target, const State &state) { 
    if(target < 0) return; // assuming we don't allow any negatives 
    if(ip==end && target==0) { 
     state.dump(); 
     return; 
    } 
    if(ip==end) 
     return; 
    { // without the first one 
     ss(ip+1, end, target, state); 
    } 
    { // with the first one 
     int first = *ip; 
     ss(ip+1, end, target-first, State(first, state)); 
    } 
} 

int main() { 
    int a[] = { 2,59,3,43,5,9,8,62,10,4 }; 
    int * start = &a[0]; 
    int * end = start + sizeof(a)/sizeof(a[0]); 
    ss(start, end, 12, State()); 
}

來源

2010-07-21 21:13:46

愛你的解決方案。謝謝。 – user373215 2010-07-21 22:23:14

@nsivakr，如果你知道一些關於數字的位表示的話，也許還有進一步的優化。例如，如果目標是一個奇數，並且集合中只有一個奇數，那麼您知道必須包含該數。然後搜索可以修剪哪裏很容易證明解決方案是不可能的。如果你期望在集合中會有很多重複，那麼會有很多冗餘。解決方法是修改「ss（ip + 1，end，target，state）;」使得它不僅跳過第一個元素，而是跳過與第一個元素相同的所有元素。 – 2010-07-27 12:26:33

這是NP-complete Knapsack Problem的變型中，subset sum problem。全面的揹包問題可以通過連續降低N線性地降低到問題的範圍內。如果P！= NP成立，您將無法找到問題的確切算法，該算法在N中的運行速度快於指數級。

但是多項式時間近似值是已知的。

來源

2010-07-21 19:06:31

您描述的問題也被稱爲Subset Sum Problem這是NP-complete。最好的你可以實現的是一種指數時間算法，它會嘗試所有可能的數組/集合的子集。

來源

2010-07-21 19:07:50

其實，只要數字都是正數，因爲它們是在nsivakr的例子中，問題在於P（我認爲）。有了正數，你知道什麼時候你超過了目標。 – 2010-07-21 19:09:58

@Pontus我不同意。原型揹包問題用非負數形成。 – 2010-07-21 19:12:57

@Pontus即使這個數字是正數，問題也是NP-Complete。如果我很好地理解你，問題要求確切的總和。 – kunigami 2010-07-21 19:14:49

這是子集總和問題（NP-Complete），直到P？= NP，只有指數解。

從xkcd

來源

2010-07-21 19:12:57 SlavaNov

@尼爾：來吧，我們已經有足夠的xkcd在笑話線程已經和這只是竊取屏幕房地產，可能使其他答案可見而不滾動。 – 2010-07-21 20:37:33

如果值都不大，說你和由M界，你可以使用dynamic programming。假設有N個項目。

想象一下你有一個矩陣DP[M][N]。單元格DP[m][n]表示：前n個元素的多少個組合恰好總和爲m？

分析每個項目，你可能會或可能不包含它在一些組合。然後，你得到的復發（照顧外的約束值）

DP[m][n] = DP[m][n-1] + DP[m - v[n]][n - 1]

RHS的第一項意味着你正在考慮不使用的第n項和第二項是做所有款項的所有款項使用第n項。您從基礎DP[0][0] = 1開始，因爲空集合是總和爲0的有效組合。所需值在DP [M] [N]中。

雖然這是僞多項式，但是O(MN)。

來源

2010-07-21 19:23:33 kunigami

+1 OP的實際問題可能會實現附加限制 – 2010-07-21 19:35:18

如果他試圖列出可能性，這並不會真正起到幫助作用。這隻會算他們。此外，你可以用一個矢量做到這一點，你不需要矩陣。 – IVlad 2010-07-21 19:35:41

@ |弗拉德：你說得對。所以沒有希望，因爲輸出可能有指數規模。我知道它可以用矢量來完成，但用矩陣解釋算法似乎更容易。 – kunigami 2010-07-23 20:57:45

這與數論中的Partition有關，可以用動態規劃來解決。

讓總數爲n。讓parts成爲元素列表。我們假設它們是正整數。

if parts == [] 
then f(n,parts) = [] 
else let parts = x::queue and f(n,parts) = union(L1, L2) 

where: 

L1 = f(n, queue) 

if n-x>0 
then let result = f(n-x, queue) and L2 = concatenation([x], result) 
else if n-x==0, L2 = [x] 
else L2 = []

這是一個typical作業。

來源

2010-07-21 19:28:34 Wok

如何找到所有匹配的數字，在給定的數組中的總和爲'N'

回答

相關問題