Knapsack 0/1 problem last test case not passing output

#1

although i have correctly used memoization concept to solve knapsack problem but it is not passing all the test cases .it passed on 4 test cases but it couldn’t pass 5th test case

#2

hey @ANUBHAV please share your code through ide.codingblocks.com

#3

#include<bits/stdc++.h>
using namespace std;
int dp[1002][1002];
int knapsack(int wt[],int val[],int s,int n)
{
if(n==1 || s==1)
return 0;
if(dp[n][s]!=-1)
return dp[n][s];
if(wt[n-1]<=s)
{
dp[n][s]=max(val[n-1]+knapsack(wt,val,s-wt[n-1],n-1),knapsack(wt,val,s,n-1));
}
else
{
dp[n][s]=knapsack(wt,val,s,n-1);

}
	return dp[n][s];

}
int main() {
memset(dp,-1,sizeof(dp));
int n,s;
cin>>n>>s;
int wt[n],val[n];
for(int i=0;i<n;i++)
{
cin>>wt[i];
}
for(int i=0;i<n;i++)
{
cin>>val[i];
}
int maxi=knapsack(wt,val,s,n);
cout<<maxi<<endl;
return 0;
}

#4
#5

@ANUBHAV in the function int knapsack, return 0, when n == 0 or s ==0 NOT when n == 1 or s == 1
Here is your code after rectification

#6

sorry wrog code sent …but even after s==0 || n==0 it will not pass 5th test case …u can check it again…i apologize for sending u wrong code

#7

hey @ANUBHAV code i provided you is passing all the test cases, please try submitting the code i sent you.

#8

please submit the same code on geeks for geeks practice questions for 0-1 knasack problem…it is not passing all the test cases

#9

@ANUBHAV that question’s input come in different manner off course it’ll fail, here is code with correct input pattern https://ide.codingblocks.com/s/193129.

#10

hey its amazing but it is exactly same as my code …can u tell me please where i went wrong ??and what changes have made?

#11

actually in the geekkforgeeks question there were test cases and values were given before in weights but in codingblocks question there were no test cases and weights were given before the values so i just changed the input order nothing else and your code was correct to begin with so it worked :slight_smile:

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.