What is wrong with my top down knapsack dp approach?

Правка en5, от TheLazyBoy, 2022-08-24 19:43:42

I am not able to figure out what is wrong with my top down knapsack dp approach, its failing testcases, need help. A= 5, 9, 1, 9, 7 and B= 3, 1, 3, 3, 2 and C=9 expected ans is 30 and the code is giving 26

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);
    }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский TheLazyBoy 2022-08-24 19:43:42 2 Tiny change: ' testcases. need help' -> ' testcases, need help'
en4 Английский TheLazyBoy 2022-08-24 19:43:12 16 Tiny change: ' testcases on below link, need help' -> ' testcases. need help'
en3 Английский TheLazyBoy 2022-08-24 17:56:10 128
en2 Английский TheLazyBoy 2022-08-24 17:30:53 2
en1 Английский TheLazyBoy 2022-08-24 17:24:07 926 Initial revision (published)