动态规划 - C++ 中的 canSum 记忆

Question

如果 sum 可以通过将给定向量中的元素相加得到，则 objective 与 return 相符。矢量元素可以按任何顺序使用和重复使用。

示例：

总和 = 7，列表 = [4,5]

return false 因为你不能使用这些列表元素来制作 7

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

return 正确，因为 9 = 4+5，5 已经在列表中，20 = 5+5+5+5，8 = 4 + 4

我不知道为什么 canSum 没有 returning 任何东西。当targetSum达到0时，canSum应该returntrue，然后在memo我们emplace（余数，真）。但是，该程序没有 returning 任何东西。这是为什么？

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

Answer 1

您的代码中的问题是您在 memo table 中处理状态存储的方式。只有在 for 循环中需要结果时才存储，同样的问题是 return 使用备忘录 table 时。因此，在完整的递归调用结束并且您退出循环之前，导致 false 的状态不会存储在您的备忘录中。因此，您的递归会一次又一次地计算相同的状态。您的逻辑是正确的，但递归代码中的动态编程集成不正确。你的代码会给出一个输出，你只需要等待很长时间，即使是一个很小的输入。下面我对上面提到的问题进行了详细的解释。

你 return 来自 memo 仅当结果为真时，即 if 条件：
```
...
if(memo[remainder] == true)
    return true;
...
```
是问题所在。我们使用动态规划来保存已经计算出的状态的结果，这样以后如果遇到同样的问题，我们就不用重新计算了，我们可以return它的结果保存memo table 以避免再次进入递归。我们 return 来自 memo table 的结果而不考虑结果。但是，只有当结果为真时，您才 returning。你应该改用这个：
```
...
if (memo.find(targetSum)!=memo.end())
    return memo[targetSum];
...
```
这也是您在 for 循环中将结果存储在备忘录 table 中时的问题。 for循环中的if条件：
```
for (auto i : vec) {
    remainder = targetSum - i;
    if (canSum(remainder, vec, memo)) {
        memo.emplace(remainder, true);
        return true;
    }
}
```
是问题所在。我们将结果存储在 memo table 中，而不考虑我们想要的结果。

这是修复了两个问题的完整代码。

#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 没有 return 任何东西。”的答案。

现在一般不应该使用递归 DP，因为它太耗时，而迭代 DP 最适合竞争性编程问题。

Answer 2

我认为这段代码来自 freecodecamp 视频。我已经解决了如下相同的问题。这里，0 表示假，1 表示真。我希望你能理解：

#include<bits/stdc++.h>
using namespace std;

vector<int>memo(1000,10);


bool canSum(int n, vector<int>v){

if(n==0){
     return true;
}
if(n<0) return false;
if(memo[n]==1) return true;
if(memo[n]==0) return false;

for(int i = 0; i<v.size(); i++){

    int rmndr = n-v[i];
    bool x = canSum(rmndr,v);
    if(x){
        memo[n] = 1;
        return true;
    }
    else{
        memo[n] = 0;
    }
    }
    return false;
}



int main() {
int n,x;
cin>>x;
vector<int>v(x);
for(int i = 0; i<v.size(); i++){
    cin>>v[i];
}
cin>>n;

if(canSum(n,v)) cout<<"true"<<endl;
else cout<<"false"<<endl;


return 0;
}

Answer 3

这就是您要找的东西

#include <vector>
#include <unordered_map>

using namespace std;

bool canSum(int target, vector<int> arr,unordered_map<int,bool> &mp){

    if(target == 0)
        return true;

    if(target < 0)
        return false;

    if(mp.find(target)!=mp.end())
        return mp[target];

    for(auto x:arr){

        int rem = target - x;
            if(canSum(rem,arr,mp) == true){

                mp[target] = true;

                return true;
            }
    }

    mp[target] = false;

    return false;

}


int main(){

int target = 300;

unordered_map<int,bool> mp;

vector <int> arr = {7,14};

cout<<canSum(target,arr,mp);

return 0;

}```

Answer 4

// memoization for the canSum problem

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool canSum(int targetSum, vector <int> &numbers, unordered_map <int,int> &memo) {
    int key = targetSum;

     if(targetSum == 0) return true;  
     if(targetSum < 0) return false; 
     if(memo.find(key) != memo.end()) return memo[key]; // to avoid duplicate subtree calculations
     else {
       for(auto x:numbers) {
      int rem = targetSum - x;

           if( canSum(rem, numbers, memo) == true) {
            memo[key] = true;
            return true;
         }

       }

    memo[key] = false;
    return false;
   }

}


 int main() {
     unordered_map <int,int> mp1;
     unordered_map <int,int> mp2;
     unordered_map <int,int> mp3;
     unordered_map <int,int> mp4;
     unordered_map <int,int> mp5;

   vector <int> nums{2,3};
   vector <int> nums1{7,14};
   vector <int> nums2{5,3,4,7};
   vector <int> nums3{2,4};
   vector <int> nums4{2,3,5};
   cout<<canSum(7,nums,mp1)<<"\n"; 
   cout<<canSum(7,nums2,mp2)<<"\n"; 
   cout<<canSum(7,nums3,mp3)<<"\n"; 
   cout<<canSum(8,nums4,mp4)<<"\n"; 
   cout<<canSum(300,nums1,mp5)<<"\n"; 

     return 0;
 }

Output of the code: 1 stands for 'true' and 0 stands for 'false'

动态规划 - C++ 中的 canSum 记忆

Dynamic programming - canSum memoization in C++

c++

dynamic-programming