c++ - 比较从递归树分支返回的 vector

Question

假设我有一个给定的总和，比如 sum = 4。我还得到一个 vector = {2,4}。有两种方法可以从给定的 vector 中生成给定的总和(元素可以重复使用)。一种方法是 {4} 导致 4 = 4。第二种方式是 {2,2} 导致 2 + 2 = 4。我必须找到可能的最短组合，因此在这种特殊情况下答案是 {4}。

这是我的方法 - 我遍历树，当在叶子上得到 0 时，我们达到基本情况，返回 {} vector ，并在遍历树时填充 vector 。当我到达一个节点时，我选择两个(或更多) vector 中较小的一个。这样当我到达根节点时，我应该得到一个可以产生目标总和的最短组合的 vector 。

到目前为止，我并不关心时间限制，我知道有很多重复的计算正在进行，所以一旦我得到正确的基本版本，我就必须记住它。

我一直在试图弄清楚为什么这段代码不起作用。任何见解将不胜感激。

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> findBestSum(int targetSum, const vector<int> &elements, vector<vector<int>> &temp) {
    if (targetSum == 0)
        return {};
    else if (targetSum < 0)
        return {-1};
    else {
        vector<int> small;
        for (auto &i : elements) {
            int remainder = targetSum - i;
            vector<int> returnedVector = findBestSum(remainder, elements, temp);
            if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty()) {
                returnedVector.push_back(i);
                temp.push_back(returnedVector);
            }
            int smallestLength = temp[0].size();
            for (auto &j : temp)
                if (smallestLength >= j.size())
                    small = j;
        }
        return small;
    }
}

int main() {
    int targetSum = 6;
    const vector<int> elements{2, 3, 5}; // answer should be [3,3] however I just get a 3...
    vector<vector<int>> temp;
    vector<int> bestSumVector = findBestSum(targetSum, elements, temp);
    for (auto i : bestSumVector)
        cout << i << " ";
} 

更新(2021 年 7 月 14 日):

在忙碌了几个月之后，我试图解决这个问题，这次我的代码如下所示:

#include <iostream>
#include <vector>
#include <map>
#include <numeric>

using namespace std;

bool howSum(int &targetSum, vector<int> &elementVector, vector<int> &howSumVector, vector<vector<int>> &allSums) {
    static int originaltargetsum = targetSum;
    if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else {
        for (auto i : elementVector) {
            int remainder = targetSum - i;
            bool flag = howSum(remainder, elementVector, howSumVector, allSums);
            if (flag) {
                howSumVector.push_back(i);
                if (targetSum == originaltargetsum ||
                    accumulate(howSumVector.begin(), howSumVector.end(), 0) == originaltargetsum) {
                    allSums.push_back(howSumVector);
                    howSumVector.clear();
                }
                return true;
            }
        }
        return false;
    }
}

int main() {
    int sum = 8; 
    vector<int> elements = {1, 4, 5}; 
    vector<vector<int>> allSums = {};
    vector<int> workingBench = {};
    howSum(sum, elements, workingBench, allSums);
    for (auto &i : allSums) {
        for (auto &j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
}
 

为此，我将 sum 作为 8 并将 elements 作为 {1, 4, 5}。此外，我现在正在存储和显示所有可能的解决方案(一旦正确完成，找到最短 vector 和内存应该很容易)。在这种情况下可能的解决方案是:

[1, 1, 1, 1, 1, 1, 1, 1]
[4, 4]
[5, 1, 1, 1]
[4, 1, 1, 1, 1]

目前我的代码只显示第一个可能的组合。我很确定我返回的 true 和 false 不正确，请帮帮我。

Answer 1

我试了一下。我确实有一个可行的解决方案，希望它是您想要的:

#include <iostream>
#include <vector>
#include <algorithm>

void howSum(int targetSum, const std::vector<int> & elementVector, const std::vector<int> & howSumVector, std::vector<std::vector<int>> & allSums)
{
    static int originaltargetsum = targetSum;

    if (targetSum == 0)
    {
        allSums.push_back(howSumVector);
        return;
    }
    else if (targetSum < 0)
    {
        return;
    }
    else
    {
        for (const auto i : elementVector)
        {
            // an element less than or equal to 0 would cause an infinite loop
            if (i <= 0)
                continue;

            std::vector<int> newSumVector = howSumVector;
            newSumVector.push_back(i);

            std::vector<int> newElementVector;
            std::copy_if(std::begin(elementVector), std::end(elementVector), std::back_inserter(newElementVector), [i](int element){ return element >= i; });

            howSum(targetSum - i, newElementVector, newSumVector, allSums);
        }
    }
}

int main()
{
    int sum = 8;
    std::vector<int> elements = { 1, 4, 5 };
    std::vector<std::vector<int>> allSums = {};
    std::vector<int> workingBench = {};

    howSum(sum, elements, workingBench, allSums);

    for (const auto & i : allSums)
    {
        for (const auto & j : i)
        {
            std::cout << j << " ";
        }

        std::cout << std::endl;
    }

    return 0;
}

我认为，一般来说，您对问题的思考过度或设计过度。就像其他人提到的那样，您当前的代码返回 true 太早了，除了第一个元素/组合之外没有任何测试。对于递归，注意返回案例很重要 - 实际上，您只需要一两个基本案例，否则您想要重复出现。

对于我这里的解决方案，我添加的主要内容是为您需要测试的每个元素复制当前的元素组合。这解决了您不测试每个数字组合的主要问题。除此之外，当达到 targetSum 时，追加到 allSums 似乎更好。通过这些更改，我能够取消 bool 返回值并稍微简化代码。运行上面的代码给出了这些解决方案:

1 1 1 1 1 1 1 1
1 1 1 1 4
1 1 1 4 1
1 1 1 5
1 1 4 1 1
1 1 5 1
1 4 1 1 1
1 5 1 1
4 1 1 1 1
4 4
5 1 1 1

这确实有一些重复项(因为测试的顺序)，但我觉得它已经足够好了，因为您只需要最小的解决方案，4 4。要找到它，您只需要按内部 vector 大小对 allSums vector 进行排序，然后取第一个条目。