0

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

PSこれは私が助けになる場合に備えて与えられた情報です。 http://dl.dropbox.com/u/9609070/Photo/Pepsi.tiff

4

1 に答える 1

1

私は先に進み、総当たり的なものを作りました。長時間稼働させておけば仕事は完了しますが、人よりもはるかに速いことは間違いありません。テストを容易にするために整数のリストを使用したので、すべての int は double でなければなりません。

#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.840 秒

これが最善の解決策だとは言いませんが、うまくいきます。もちろん、あなたのリストは私が与えたものに比べてかなり大きいので、もっと時間がかかります.

ああ、これのいくつかはコンパイルに C++11 を必要とします。それは、範囲付き for ループと二重の直角ブラケットだけかもしれません。それらはで修正できます

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

と

vector<vector<int> > v;

それぞれ。これにより、妥当な時間内に仕事が完了するかどうかを乾杯します。

編集：

for (const auto &element : sub)...と置き換えます

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;
    }

std::for_each内部にアクセスする必要があるという事実がなければ、置き換え可能であるfoundため、明示的なループに戻ります。

于 2012-04-19T21:53:17.243 に答える