i am trying to solve 01 knapsack problem using memorisation but my code is giving wrong answer. can somebody pls tell why?
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to return max value that can be put in knapsack of capacity W.
int solve(int w,int wt[],int val[],int n,int i,vector<vector<int>> &dp){
cout<<i<<endl;
if(i=n-1)
{
if(w>=wt[i])
return val[i];
else
return 0;
}
if(dp[i][w]!=-1)
return dp[i][w];
int include=-2,exclude;
if(wt[i]<= w)
include=solve(w-wt[i],wt,val,n,i+1,dp)+val[i];
exclude= solve(w,wt,val,n,i+1,dp);
return dp[i][w]=max(include,exclude);
}
int knapSack(int W, int wt[], int val[], int n)
{
// Your code here
vector<vector<int>> dp(n,vector<int>(W+1,-1));
solve(W,wt,val,n,0,dp);
return dp[n-1][W];
}};
Problem Link: 0 - 1 Knapsack Problem | Practice | GeeksforGeeks