0-N knapsack----------

#1

why this code will not work
int knapsack(int* arr,int* val,int n,int s){
if(n==0||s<=0)
return 0;
if(dp[n][s]>-1){
return dp[n][s];
}
int a=-1,b=-1;
if(s>=arr[n-1]){
a=val[n-1]+knapsack(arr,val,n,s-arr[n-1]);
}
b=knapsack(arr,val,n-1,s);
return dp[n][s]=max(a,b);

}

its like if i take i item then then i reduce weight but donot change size of array as i still keep it in my array to be used again
and if i don’t take it then remove it by decreasing the size n-1
similarly as we do in coin change problem to result checking all possible combinations

#2

@riprogerdep your logic is correct implement this in your code it will work fine.

#3

#include <bits/stdc++.h>
using namespace std;

int dp[1005][1005];
int knapsack(int* arr,int* val,int n,int s){
if(n==0||s<=0)
return 0;
if(dp[n][s]>-1){
return dp[n][s];
}
int a=-1,b=-1;
if(s>=arr[n-1]){
a=val[n-1]+knapsack(arr,val,n,s-arr[n-1]);
}
b=knapsack(arr,val,n-1,s);
return dp[n][s]=max(a,b);

}

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

this solution of mine is not working

#4

@riprogerdep 2nd dimension of your dp shuold be upto 100005 since S can be upto 100000 update it.

#5

#include <bits/stdc++.h>
using namespace std;

int dp[1005][100005];
int knapsack(int* arr,int* val,int n,int s){
if(n==0||s<=0)
return 0;
if(dp[n][s]>-1){
return dp[n][s];
}
int a=-1,b=-1;
if(s>=arr[n-1]){
a=val[n-1]+knapsack(arr,val,n,s-arr[n-1]);
}
b=knapsack(arr,val,n-1,s);
return dp[n][s]=max(a,b);

}

int main() {
int n,s;
//memset(dp,-1,sizeof(dp));
cin>>n>>s;
int* arr=new int[n+1];
int* val=new int[n+1];
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
cin>>val[i];
}
cout<<knapsack(arr,val,n,s)<<endl;
}
still not working
i think you should try once

#6

okay check this i have implemented the same (https://ide.codingblocks.com/s/187820)

#7

thanks for the explanation bhai that code wworks fine but as explained in the video with the help of 1-d array using iterative approach i cleared all the test cases but when i tried to implement that logic recursively i faced problem plz check it
link:-

#8

@riprogerdep this code is correct it should work.

#9

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.