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

Question

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

附言这是我得到的信息，以防有帮助。 http://dl.dropbox.com/u/9609070/Photo/Pepsi.tiff

Answer 1

我继续进行暴力破解。如果让它运行很长时间，它会完成工作，但肯定比人快得多。我使用了一个整数列表以使其更易于测试，因此每个整数都应该有一个 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;
    }

如果不是因为您需要访问内部的 found ，它可以用 std::for_each 替换，所以它返回到一个显式循环。