Hey! I was trying to do knapsack in a reverse manner. Please help. Filling last column, last row of matrix by 0s first.
Can please spot the error what am I doing wrong?
class Solution
{
public:
//Function to return max value that can be put in knapsack of capacity W.
int knapSack(int W, int wt[], int val[], int n)
{
int dp[1001][1001];
// Your code here
for(int i=n; i>=0; i–){
for(int j=W; j>=0; j–){
if(i==n || j==W ){
dp[i][j]=0;
}
if(wt[i]>W){
dp[i][j]=dp[i+1][j];
}
else{
dp[i][j]=max(dp[i+1][j],dp[i+1][j-wt[i]]+val[i]);
}
}
}
return dp[0][0];
}
};