c++ - 给出数字列表以确定哪个组合为您提供给定值

Question

好的，所以我的编程技能真的很新手而且超级生疏，但这是我的问题。我需要一种方法来获取给定数字的列表并将它们以所有组合加在一起以确定哪个组合等于一定数量。我的妻子在百事可乐工作，他们必须手工完成，她让我帮助她。如果可能的话，我会用 C++ 来尝试这个。多谢你们。

PS这是我得到的信息，以防万一。 http://dl.dropbox.com/u/9609070/Photo/Pepsi.tiff

Answer 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.840s

我并不是说这是最好的解决方案，但它确实有效。当然，与我提供的清单相比，您的清单相当大，因此需要更长的时间。

哦，其中一些需要 C++11 编译。它可能只是 ranged-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，因此它回到了显式循环。