Whats wrong with my top down knapsack dp approach?

Question

I am not able to figure out what is wrong with my top down knapsack dp approach, its failing testcases on below link, need help.

Question link: https://www.interviewbit.com/problems/0-1-knapsack/

Here is my code:

  int fin(int i,int wt,int curprofit,vector<int>&A,vector<int>&B,int C,int n,vector<vector<int>>&dp)
    {
        if(i==n)
            return curprofit;
        if(dp[i][wt]!=-1)
        return dp[i][wt];
        int ret=0;
        ret=max(ret,fin(i+1,wt,curprofit,A,B,C,n,dp));
        if(wt+B[i]<=C)
        {
            ret=max(ret,fin(i+1,wt+B[i],curprofit+A[i],A,B,C,n,dp));
        }
        return dp[i][wt]= ret;
    }
    int Solution::solve(vector<int> &A, vector<int> &B, int C) {
        int n=A.size();
        vector<vector<int>>dp(n+1,vector<int>(C+1,-1));
        return fin(0,0,0,A,B,C,n,dp);
    }

Answer 1

Here's the fix, but I'd suggest you brush up on your recursion knowledge.

Calculate the max profit on the fly, not passing as the parameter. Otherwise, you'll need to put curprofit also in the dp state which will be costly. You may also see the output by removing the dp[][] caching. Just put up a correct recursive solution & memoize it.

int fin(int i,int wt,vector<int>&A,vector<int>&B,int C,int n,vector<vector<int>>&dp)
    {
        if(i==n)
            return 0;
        if(dp[i][wt]!=-1)
        return dp[i][wt];
        int ret=0;
        ret=max(ret,fin(i+1,wt,A,B,C,n,dp));
        if(wt+B[i]<=C)
        {
            ret=max(ret,fin(i+1,wt+B[i],A,B,C,n,dp) + A[i]);
        }
        return dp[i][wt]= ret;
    }
    int Solution::solve(vector<int> &A, vector<int> &B, int C) {
        int n=A.size();
        vector<vector<int>>dp(n+1,vector<int>(C+1,-1));
        return fin(0,0,A,B,C,n,dp);
    }