一個數組算法的組合

Question

我想找到一個大小爲5的數組的組合，最多可以有15個。最好的辦法是這樣做。

假設我有陣列

7 8 10 5 3 

什麼是發現了在C++中添加15個全數字

Answer 1

如您在評論中提到的那樣，10是問題中的最高數字（也是最大元素數量）。然後蠻力（用聰明bitmasking，見this tutorial）會做：

// N is the number of elements and arr is the array. 
for (int i = 0; i < (1 << N); ++i) { 
    int sum = 0; 
    for (int j = 0; j < N; ++j) if (i & (1 << j)) sum += arr[j]; 
    if (sum == required_sum); // Do something with the subset represented by i. 
} 

該算法複雜度爲O（N * 2^N）。注意，代碼是正確的，只要N < 32.注意，具有一定和的子集的數目可以是指數的（大於2 ^（N/2））。例如，{1,1,1,1，...，1}和sum = N/2。

然而，如果N較大，但N * required_sum不是非常大（高達數百萬），可以使用下面的復發（用動態編程或記憶化）：

f(0, 0) = 1 
f(0, n) = 0 where n > 0 
f(k, n) = 0 where k < 0 
f(k + 1, S) = f(k, S - arr[k]) + f(k, S) where k >= 0 

其中f（K ，S）表示用元素0..k的子集獲得總和S的可能性。動態編程表可用於生成所有子集。生成表的運行時間是O（N * S），其中S是所需的總和。從表中生成子集的運行時間與這些子集的數量成比例（可能非常大）。

有關該問題的一般注意事項：

的問題一般是NP-Complete。因此，它沒有已知的多項式時間算法。它確實有一個pseudo-polynomial time algorithm，即上面的重現。

Answer 2

「最好」的方式取決於你正在優化什麼是最好的方式。

如果不存在陣列中的許多元件，有一個簡單的組合學算法：對於從1到n所有長度（其中n是數組中元素的數目），檢查n數目的所有可能集合並打印各總和爲15。

從時間到實施的角度來看，這可能是最好的。從運行效率的角度來看，動態編程解決方案（這是一個DP問題）可能是最好的;這裏的DP解決方案是O(N³)，其中組合解決方案遠不止於此。

DP算法的要點（我沒有編寫代碼）是通過你的數組，並跟蹤所有可能的和你可以看到的子數組的總和。當你到達每一個新的數組元素時，通過你以前得到的所有部分和，並將它添加到它們（而不是刪除原始部分和）。每當有東西擊中15或通過它時，從你正在跟蹤的集合中丟棄該總和（如果它打到15則打印它）。

Answer 3

我的建議是去遞歸。

跟蹤的baseindex和CURRENTINDEX 並嘗試累積值每次遞歸

回報CURRENTINDEX的整數值，當累積值是15 否則如果CURRENTINDEX達到5，並且累計值是不是15返回0

當返回值爲0且baseindex仍小於5時，則將基址索引加1並重置當前索引和累加值，並再次開始遞歸。

Answer 4

遞歸是我能想到的一個選項。因爲我有一些閒暇時間在我手上，所以我把這個功能放在一起（儘管它可能不必要的大，而且沒有被優化到極限）。我只用你提供的號碼進行測試。

void getCombinations(std::vector<int>& _list, std::vector<std::vector<int>>& _output, 
         std::vector<int>& _cSumList = std::vector<int>(), int _sum = 0) 
{ 
    for (std::vector<int>::iterator _it = _list.begin(); _it < _list.end(); ++_it) 
    { 
     _sum += *_it; 
     _cSumList.push_back(*_it); 
     std::vector<int> _newList; 
     for (std::vector<int>::iterator _itn = _list.begin(); _itn < _list.end(); ++_itn) 
      if (*_itn != *_it) 
       _newList.push_back(*_itn); 
     if (_sum < 15) 
      getCombinations(_newList, _output, _cSumList, _sum); 
     else if (_sum == 15) 
     { 
      bool _t = false; 
      for (std::vector<std::vector<int>>::iterator _itCOutputList = _output.begin(); _itCOutputList < _output.end(); ++_itCOutputList) 
      { 
       unsigned _count = 0; 
       for (std::vector<int>::iterator _ita = _itCOutputList->begin(); _ita < _itCOutputList->end(); ++_ita) 
        for (std::vector<int>::iterator _itb = _cSumList.begin(); _itb < _cSumList.end(); ++_itb) 
         if (*_itb == *_ita) 
          ++_count; 
       if (_count == _cSumList.size()) 
        _t = true; 
      } 
      if (_t == false) 
       _output.push_back(_cSumList); 
     } 
     _cSumList.pop_back(); 
     _sum -= *_it; 
    } 
} 

用法示例與你的號碼：

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    std::vector<int> list; 
    list.push_back(7); 
    list.push_back(8); 
    list.push_back(10); 
    list.push_back(5); 
    list.push_back(3); 
    std::vector<std::vector<int>> output; 
    getCombinations(list, output); 
    for (std::vector<std::vector<int>>::iterator _it = output.begin(); _it < output.end(); ++_it) 
    { 
     for (std::vector<int>::iterator _it2 = (*_it).begin(); _it2 < (*_it).end(); ++_it2) 
      std::cout << *(_it2) << ","; 
     std::cout << "\n"; 
    } 
    std::cin.get(); 
    return 0; 
} 

最好的辦法是主觀的。正如我所說，上面的代碼可以大大改善，但應該給你一個出發點。

Answer 5

排序元素的數組。 維護兩個指針，一個在排序數組的開始處，另一個在結尾處。 如果兩個元素的總和大於15，則減少第二個指針。 如果總和小於15，則增加第1個指針。 如果sum等於15，則記錄這兩個元素，並增加第一個指針。

希望它有效。