c++ - 对 vector 中的整数序列求和

Question

我有函数 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;
}

它可以工作，但即使 vector 大小仅为 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

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