-2

sum如果可以通过将给定向量中的元素相加来实现，则目标是返回 true 。矢量元素可以以任何顺序使用和重用。

例子：

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

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

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

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

我不知道为什么canSum不返回任何东西。当targetSum达到 0 时，canSum应该返回true，然后在memowe emplace(remainder, true)。但是，该程序没有返回任何内容。这是为什么？

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

4 回答 4

2

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

  1. 仅当结果为真时才返回，memo即 if 条件：

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

    是问题所在。我们使用动态规划来保存已经计算的状态的结果，这样如果我们以后遇到同样的问题，我们不必重新计算它，我们可以从保存的memo表中返回它的结果，以避免再次进入递归. memo无论结果如何，我们都会从表中返回结果。但是，只有当结果为真时，您才会返回。你应该改用这个：

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

  2. 当您将结果存储在 for 循环中的备忘录表中时，这也是问题所在。for循环中的if条件：

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

    是问题所在。memo无论我们想要的结果如何，我们都将结果存储在表中。

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

#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不返回任何东西”的答案。

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

于 2021-03-20T20:28:15.657 回答
-1

这就是你要找的

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

}```
于 2021-10-23T21:52:10.193 回答
-1 
// 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;
 }

代码输出：1代表“真”，0代表“假”

于 2021-11-11T06:21:15.323 回答
-1

我认为这段代码来自 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;
}
于 2021-08-06T06:22:24.507 回答