比较从递归树分支返回的向量

Question

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

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

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

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

#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}。此外，我现在正在存储和显示所有可能的解决方案（一旦正确完成，找到最短向量和记忆应该很容易）。在这种情况下可能的解决方案是：

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

目前我的代码只显示了第一个可能的组合。我很确定我 returning true 和 false 不正确，请在这里帮助我。

Answer 1

我认为您需要更改实现以正确处理向量的元素。在您的实现中，它不会遍历所有矢量项，只是第一个。如果您使用向量元素作为函数中的第一个参数，这是一种实现方法。

vector<int> findBestSum(int element, int targetSum, const vector<int>& elements, 
vector<vector<int>>& temp) {
if (targetSum == 0)
    return {};
else if (targetSum < 0)
    return { -1 };
else {
    int remainder = targetSum - element;
    vector<int> returnedVector = findBestSum(element, remainder, elements, temp);
    if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty()) {
        returnedVector.push_back(element);
        return returnedVector;
    }
    return returnedVector;
}

}

int main() {
  const 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;
  for (auto i : elements) {
      vector<int> returnedVector = findBestSum(i, targetSum, elements, temp);
      if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty())
          temp.push_back(returnedVector);
  }

  if (temp.size() > 0) {
      vector<int> bestSum = {};
      size_t small = 0;
      size_t smallestLength = temp[0].size();
      for (auto& j : temp)
          if (smallestLength >= j.size()) {
              small = j.size();
              bestSum = j;
          }
      for (auto i : bestSum)
          cout << i << " ";
    }
    else
        cout << " sum not found" << endl;
}

Answer 2

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

#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;
}

我认为，总的来说，您对问题的思考过度或设计过度。就像其他人提到的那样，您当前的代码 returning true 太早了，除了第一个 element/combination 之外没有任何测试。对于递归，在你的 return 案例中小心是很重要的 - 实际上，你只需要一个或两个基本案例，否则你想要递归。

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

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。要找到它，您只需要按内部向量大小对 allSums 向量进行排序，然后取第一个条目。

比较从递归树分支返回的向量

Comparing returned vectors from recursion tree branches

c++

recursion

dynamic-programming

subset-sum