假设我有一个给定的和，比如sum=4。我还得到了一个向量＝{2,4}。有两种方法可以从给定的向量生成给定的和(元素可以重复使用(。一种方法是｛4｝，因为4＝4。第二种方法是{2,2}导致2+2=4。我必须找到尽可能短的组合，因此在这种特殊情况下，答案是{4}。
这是我的方法——我遍历树，当在叶子上得到0时，我们击中基本情况，返回{}向量，并在遍历树的同时填充向量。当我到达一个节点时，我会选择两个(或多个(向量中较小的一个。这样，当我到达根节点时，我应该得到一个最短组合的向量，它可以产生目标和。
到目前为止，我不在乎时间限制，我知道有很多重复的计算在进行，所以一旦我能得到正确的基本版本，我就必须记住它。
我一直在想为什么这个代码不起作用。任何见解都将不胜感激。
#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]
目前，我的代码只显示第一个可能的组合。我确信我错误地返回了true和false，请在这里帮助我。
我尝试了一下。我确实有一个有效的解决方案，希望它是你想要的：
#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。要找到它，您只需要按内部向量大小对allSums向量进行排序，然后获取第一个条目。
我认为您需要更改实现以正确处理向量的元素。在您的实现中，它不会遍历所有向量项，只遍历第一个向量项。如果使用向量元素作为函数中的第一个参数，这是一种方法。
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;
}