[背包中使用回忆的标题

Question

问题陈述：给定n个大小为Ai的物品，整数m表示背包的大小。您可以将这个背包装满吗？

示例范例1：输入：[3,4,8,5]，背包尺寸= 10输出：9

示例2：输入：[2,3,5,7]，背包尺寸= 12输出：12

我必须使用备忘录来编写解决方案，我知道自下而上的dp将会非常快，但是您能为我提供可以添加到此解决方案中的其他优化吗？

class Solution {
public:
    unordered_map<string,int>m1;
    int solve(int m,vector<int>&a,int i){
        if(i<0)return 0;

        string s = to_string(m)+" "+to_string(i);
        if(m1.count(s))return m1[s];
        int val=0;
        if(m-a[i]>=0)val = a[i] + solve(m-a[i],a,i-1);
        return m1[s]=max(val,solve(m,a,i-1));

    }
    int backPack(int m, vector<int> &a) {
        // write your code here
       return solve(m,a,int(a.size()-1));
    }
};

Answer 1

考虑采用类似m的方法来创建两个整数i和this的散列并将其用作地图中的键。尽管自下而上的解决方案更胜一筹，但您应该看到运行时有所改进。在您的代码中，to_string需要时间，并且查找字符串所花费的时间也要比注释中提到的要多。