1

Problem Statement: Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Example Example 1: Input: [3,4,8,5], backpack size=10 Output: 9

Example 2: Input: [2,3,5,7], backpack size=12 Output: 12

I have to write solution using memoization , I know bottom up dp will be quite fast ,But can you help me with other optimisation that i can add in this solution. 

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));
    }
};
ddddddd
  • 11
  • 1

1 Answers1

0

Consider creating a hash of two integers m and i by following an approach like this and use that as key in your map. You should see an improvement in runtime although bottom up solution is superior. In your code, the to_string takes time and also it takes more time to look up for the string than you think as mentioned in the comments.

SomeDude
  • 13,876
  • 5
  • 21
  • 44