#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
int t[102][1002]={-1};
int knapsack(int wt[],int val[],int w,int n)
{
if(n==0 || w==0)//base case
return 0;
if(t[n][w]!=-1)
{
return (t[n][w]);
}
if(wt[n-1]<=w)
{
t[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1),knapsack(wt,val,w,n-1));
return t[n][w];
}
else if(wt[n-1]>w)
{
t[n][w]=knapsack(wt,val,w,n-1);
return(t[n][w]);
}
}
int main()
{
int n,w;
cin>>n>>w;
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];
}
cout<<knapsack(wt,val,w,n);
return 0;
}
int t[102][1002]={-1};
This does not work. It will set t[0][0]
to -1
and the rest will be 0
.
But every where in solutions they use memset to initialize the 2d array with zero. How should fix this.
Sorry initialize with -1*
Check the method three, here also whole array is initialized with -1.
I m still noob, please be patient and help❣️
Yes, memset
will work for setting all values to 0
or -1
. Two things, though:
- You didn’t use
memset
- Don’t use it for other values. Only for
0
and-1
, unless you actually understand how it works.
Got it. Thanku so much. U helped me last time also. Thanku so much.
#include
#include <bits/stdc++.h>
using namespace std;
int static t[100][1000];
memset(t,-1,sizeof(t));
int knapsack(int wt[],int val[],int w,int n)//recursive->memoize.
{
if(n==0 || w==0)//base case{smallest valid input}
return 0;
if(t[n][w]!=-1)
{
return (t[n][w]);
}
if(wt[n-1]<=w)//{choice}
{
t[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1),knapsack(wt,val,w,n-1));
return t[n][w];
}
else if(wt[n-1]>w)
{
t[n][w]=knapsack(wt,val,w,n-1);
return(t[n][w]);
}
}
int main()
{
int n,w;
cin>>n>>w;
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];
}
cout<<knapsack(wt,val,w,n);
return 0;
}
now its giving: error: expected constructor, destructor, or type conversion before ‘(’ token
memset(t,-1,sizeof(t));
i even tried putting memset inside main function then its returns zerro without an error
Please fix this code and share,please.
Sir, do respond please.
ok will do that thanks.
#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
int t[100][100];
int knapsack(int wt[],int val[],int w,int n)//recursive->memoize.
{
if(n==0 || w==0)//base case
return 0;
if(t[n][w]!=-1)
{
return (t[n][w]);
}
if(wt[n-1]<=w)
{
t[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1),knapsack(wt,val,w,n-1));
return t[n][w];
}
else if(wt[n-1]>w)
{
t[n][w]=knapsack(wt,val,w,n-1);
return(t[n][w]);
}
}
int main()
{
int n,w;
cin>>n>>w;
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];
}
memset(t,-1,sizeof(t));
cout<<knapsack(wt,val,w,n);
return 0;
}
now please fix this code and tell me what was wrong there?
hey!
you need to fix your conditional statements.
try to replace the else if statement with just an else one.
#include
#define lli long long int
#define li long int
#define ld long double
using namespace std;
int t[100][100];
int knapsack(int wt[],int val[],int w,int n)//recursive->memoize.
{
if(n==0 || w==0)//base case
return 0;
if(t[n][w]!=-1)
{
return (t[n][w]);
}
if(wt[n-1]<=w)
{
t[n][w]=max(val[n-1]+knapsack(wt,val,w-wt[n-1],n-1),knapsack(wt,val,w,n-1));
return t[n][w];
}
else
{
t[n][w]=knapsack(wt,val,w,n-1);
return(t[n][w]);
}
}
int main()
{
int n,w;
cin>>n>>w;
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];
}
memset(t,-1,sizeof(t));
cout<<knapsack(wt,val,w,n);
return 0;
}
since the function is non void therefore you need to make sure that it has an output to print.