どの組み合わせがあなたに与えられた値を与えるのかを決める数字のリストを与えてください

Question

私のプログラミングのスキルは本当に初心者で、錆びたものですが、ここでは私の問題です。私は与えられた数のリストを取り、すべての組み合わせでそれらを一緒に加えて、どのコンボが特定の量に等しいかを決定する方法が必要です。私の妻はペプシで働き、手でこれをしなければならず、彼女は私に彼女を助けるように頼んだ。可能であれば、私はこれをC++で試していきます。みんなありがとう。

P.S.ここで私はそれが役立つincase与えられた情報です。 http://dl.dropbox.com/u/9609070/Photo/Pepsi.tiff

Answer 1

私は先に進み、ブルートフォースを行いました。それはあなたが長い間それを実行したままにすると、仕事を完了するが、間違いなく人々よりもはるかに高速です。私は、簡単にテストできるように整数のリストを使用したので、すべてのintは二重でなければなりません。

#include <algorithm> 
using std::accumulate; 
using std::distance; 
using std::includes; 
using std::next_permutation; 
using std::sort; 

#include <fstream> 
using std::ifstream; 

#include <iostream> 
using std::cout; 

#include <vector> 
using std::vector; 

int main() 
{ 
    const int wantedSum = 100; //this is your wanted sum here 

    vector<int> v; //stores all of the numbers to choose from 
    vector<vector<int>> matches; //stores combinations (no different ordering) 

    ifstream inFile ("combination sum.txt"); //file to read values from 

    int input; 
    while (inFile >> input) //fill v with values 
     v.push_back (input); 

    inFile.close(); 

    for (vector<int>::size_type subSize = 1; subSize < v.size(); ++subSize) //go from 1 element at a time to the number to choose from 
    { 
     vector<int> sub (subSize); 
     sort (v.begin(), v.end()); //sort original vector 

     do 
     { 
      for (vector<int>::iterator it = sub.begin(); it != sub.end(); ++it) //fill subvector with first n values in v 
       *it = v.at (distance (sub.begin(), it)); 

      if (accumulate (sub.begin(), sub.end(), 0) == wantedSum) //check for sum 
      { 
       sort (sub.begin(), sub.end()); //sort subvector 

       bool found = false; //check if same (but different order) as another 
       for (const auto &element : matches) 
        if (includes (element.begin(), element.end(), sub.begin(), sub.end())) 
        { 
         found = true; 
         break; 
        } 

       if (!found) //if it isn't the same as any 
       { 
        matches.push_back (sub); //push sorted vector 

        cout << '{'; //output match 

        for (const auto &element : sub) 
         cout << element << ' '; 

        cout << "\b}\n"; 
       } 
      } 
     } while (next_permutation (v.begin(), v.end())); //go onto next permutation of v (this is what causes uber slowness as v's size grows) 
    } 
} 

入力：

45 
24 
3 
79 
8 
30 
55 
27 
34 
9 

出力：

{45 55} 
{3 8 34 55} 
{9 27 30 34} 
{3 9 24 30 34} 

実行時間（あなたはおそらく高くなります）：0.840s

私はこれが最善であるとは言いませんよ解決策ですが、機能します。もちろんあなたのリストは私が与えたものに比べてかなり大きいので、ロットが長くかかるでしょう。

ああ、このうちのいくつかはC++ 11でコンパイルされます。それはちょうどranged forループと二重右山括弧であるかもしれません。彼らはそれぞれ

for_each (vec.begin(), vec.end(), some_func); //in algorithm 

と

vector<vector<int> > v; 

で固定することができます。合理的な時間内に仕事が成し遂げられれば幸いです。

編集：

、それが戻って明示的なループにありますので、あなたは、found内部にアクセスする必要があるという事実がなければそれはstd::for_eachと交換可能になり

for (vector<int>::const_iterator it = sub.begin(); it != sub.end(); ++it) 
    if (includes (element.begin(), element.end(), sub.begin(), sub.end())) 
    { 
     found = true; 
     break; 
    } 

でfor (const auto &element : sub)...を交換してください。