对向量中的整数序列求和

Question

我有函数bool exists(int sum, vector<int>& vec) 它的作用是 return vec 中是否有任何数字序列等于 sum.

例如

Vec = 140 80 90 180 70 sum = 300

函数 returns true 因为序列 140 90 70 存在并且等于 300.

现在我有代码：

bool possible(int sum, vector<int> &vec)
{
do
{
    int s = 0;
    for (int i = 0; i < vec.size(); i++)
    {
        s += vec.at(i);
        if (s == sum)
        {
            return true;
        }

    }
}while(next_permutation(vec.begin(), vec.end()));

return false;
}

有效，但即使向量大小仅为 20 也需要很长时间。

谁能帮我提供更好的方法？

Answer 1

It works

首先，它不太有效，除非 vec 被排序为开头。否则，next_permutation(...) 会在没有穷尽所有可能性的情况下产生 false，可能会跳过找到正确解决方案的排列。

but takes too long even when the vector size is just 20.

那是因为这是一个复杂度为 O(N!) 的解决方案。请注意 N! 即使对于强力解决方案也不必要地高，因为您执行添加的顺序并不重要。您只需要 O(2^N) 来尝试所有子集。

您可以通过对 0/1 knapsack problem 使用伪多项式解决方案来做得更好。这个想法是创建一组所有可能的总和，直到所需的数字 N。从单个数字零开始该集合。在每次迭代中产生另一个集合，其中包含前一次迭代中集合的所有元素，加上通过将列表中的数字添加到每个先前的总和而产生的集合，将值限制在目标数字（即 300）：

{ 0 }
{ 0, 140 } -- Added 0+140
{ 0, 80, 140, 220 } -- Added 0+80, 140+80
{ 0, 80, 90, 140, 170, 220, 230 } -- Added 0+90, 80+90, 140+90; 220+90 > 300, so it is not added
... // And so on

在此过程结束时，您将获得集合中所有可能的总和。现在您需要做的就是检查集合中的项目中是否存在您的目标编号。

Answer 2

bool possible(int sum, vector<int> &vec)
{
    int s = 0;
    for (int i = 0; i<vec.size(); i++)
    {
      s += vec.at(i);
    }

    if (s==sum)
    return true;
    else
    return false;

}

这样效率会更高，只需将矢量值相加并在最后比较结果。在这种情况下，您不会进行任何排列计算，也不需要在 do...while 循环中使用 for 循环。

Answer 3

我得到了这个工作代码。

bool possible(int sum, vector<int &vec)
{
    vector<int> previous;
    previous.push_back(0);

    for(auto i = vec.begin(); i != vec.end(); i++)
    {
        vector<int> temp(previous);
        for(auto j = temp.begin();  j != temp.end(); j++)
            *j += *i;
        for(auto k = temp.begin(); k != temp.end(); k++)
        {
            if(*k <= sum)
                previous.push_back(*k);
        }
    }
    sort(previous.begin(),previous.end());
    return binary_search(previous.begin(),previous.end(),sum);
}

谢谢大家。

对向量中的整数序列求和

Sum a sequence of integers in a vector

c++

algorithm

sequences

vector