动态编程-C ++中的canSum记忆 [英] Dynamic programming - canSum memoization in C++

问题描述

目标是如果可以通过将给定向量中的元素相加而得出 sum ，则返回true.向量元素可以按任何顺序使用和重用.

The objective is to return true if the sum can be made by adding up elements from a given vector. The vector elements maybe used and reused in any order.

示例:

sum = 7，列表= [4,5]

sum = 7, list = [4,5]

返回false，因为您不能使用这些列表元素将其设为7

return false because you can't use these list elements to make 7

sum = 9或5或20或8，列表= [4,5]

sum = 9 or 5 or 20 or 8, list = [4,5]

返回true，因为9 = 4 + 5，5已在列表中，20 = 5 + 5 + 5 + 5，8 = 4 + 4

return true because 9 = 4+5, 5 is in list already, 20 = 5+5+5+5, 8 = 4 + 4

我不知道为什么 canSum 不返回任何内容.当 targetSum 达到0时， canSum 应该返回 true ，然后在 memo 中我们 emplace (其余，正确).但是，该程序未返回任何内容.为什么会这样?

I do not know why canSum is not returning anything. When targetSum reaches 0, canSum should return true, and then in memo we emplace (remainder, true). However, the program is not returning anything. Why is that?

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

using namespace std;


bool canSum(int targetSum, vector<int> &vec, map<int, bool> &memo) {
    int remainder;
    if (memo[targetSum] == true)
        return true;
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else
        for (auto i : vec) {
            remainder = targetSum - i;
            if (canSum(remainder, vec, memo)) {
                memo.emplace(remainder, true);
                return true;
            }
        }
    memo.emplace(remainder, false);
    return false;
}

int main() {
    vector<int> vector1{7, 14};
    int sum = 300;
    map<int, bool> memo;
    if (canSum(sum, vector1, memo))
        cout << "true";
    else
        cout << "false";
}

推荐答案

代码中的问题是您处理 memo 表中的状态存储方式.仅在for循环中需要结果且使用备注表返回时出现相同问题时才存储.因此，导致错误的状态不会存储在您的备忘录中，直到完整的递归调用结束并且您处于循环之外.因此，您的递归会继续一次又一次地计算相同的状态.您的逻辑是正确的，但是在递归代码中进行动态编程集成是不合适的.您的代码将提供输出，您只需要等待很长时间，即使输入的内容很少.下面我详细解释了上述问题.

The problem in your code is the way you handle the storing of sates in your memo table. You store only when the result is desired in the for loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until the complete recursive call ends and you are out of the loop. So, your recursion keeps on calculating the same states again and again. Your logic is correct but dynamic programming integration in recursive code is not proper. Your code will give an output, you just need to wait for a long time even for a small input. Below I have explained the above mentioned problems in detail.

1. 仅当结果为true时，才从 memo 返回，即if条件:

1. You return from memo only if the result is true i.e. the if condition:

...
if(memo[remainder] == true)
    return true;
...

是问题所在.我们使用动态编程来保存已计算状态的结果，这样，如果将来遇到相同问题，就不必重新计算它，并且可以从保存的 memo table以避免再次进入递归.无论结果如何，我们都会从 memo 表返回结果.但是在这里，仅当结果为true时，您才返回.您应该改用以下方法:

is the problem. We use dynamic programming to save the result of a state that has been calculated so that if we come across the same problem in future, we don't have to recalculate it and we can return its result from saved memo table to avoid going into recursion again. We return the result from memo table irrespective of the result. But here you are returning only if the result was true. You should instead use this:

...
if (memo.find(targetSum)!=memo.end())
    return memo[targetSum];
...

1. 当您将结果存储在for循环的备注表中时，这也是问题.for循环中的if条件:

for (auto i : vec) {
    remainder = targetSum - i;
    if (canSum(remainder, vec, memo)) {
        memo.emplace(remainder, true);
        return true;
    }
}

是问题所在.无论结果如何，我们都将结果存储在备忘录表中.

is the problem. We store the result in the memo table irrespective of our desired result.

这是已修复两个问题的完整代码.

Here is the complete code with both problems fixed.

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

using namespace std;

bool canSum(int targetSum, vector<int> &vec, map<int, bool> &memo) {
    int remainder;
    if (memo.find(targetSum)!=memo.end())
        return memo[targetSum];
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else{
        bool ans = false;
        for (auto i : vec) {
            remainder = targetSum - i;
            ans = ans || canSum(remainder, vec, memo);
            if (ans) {
                memo.emplace(targetSum, true);
                return true;
            }
        }
        memo.emplace(targetSum, false);
    }
    return false;
}

int main() {
    vector<int> vector1{7, 14};
    int sum = 300;
    map<int, bool> memo;
    if (canSum(sum, vector1, memo))
        cout << "true";
    else
        cout << "false";
}

这是对您的问题我不知道为什么canSum不返回任何东西"的答案.

This is the answer to your question "I do not know why canSum is not returning anything."

现在，通常不应该使用递归DP，因为它耗时过多，并且迭代DP最适合竞争性编程问题.

Now, in general one should not use recursive DP as it is too much time consuming and iterative DP is best suited for competitive programming problems.

这篇关于动态编程-C ++中的canSum记忆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！