对向量中的整数序列求和

user3594141 发表于 Dev

用户名

我有一个函数bool exists(int sum, vector<int>& vec)，它的作用是返回是否vec等于等于的数字序列sum。

例如

Vec = 140 80 90 180 70 sum = 300

该函数返回，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，也要花费很长时间。

谁能帮我更好的方法？

谢尔盖·卡里尼琴科（Sergey Kalinichenko）

有用

首先，它不是很有效，除非vec首先进行排序。否则，next_permutation(...)将在false不穷尽所有可能性的情况下产生结果，可能会跳过找到正确解决方案的排列。

但即使向量大小仅为20，也要花费太长时间。

那是因为这是O（N！）解决方案。请注意，N!即使是蛮力解决方案，该值也不必要地很高，因为添加的顺序无关紧要。您只需要O（2 ^N）来尝试所有子集。

通过对0/1背包问题采用伪多项式解决方案，您可以做得更好。这个想法是创建一个由所有可能的总和组成的集合，直到期望的数字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

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。