Knapsack recursive memoized.please tell me why is this code not working and always returning zero

help
,
1 
#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;
}
2

int t[102][1002]={-1};

This does not work. It will set t[0][0] to -1 and the rest will be 0.

1 Like
3

But every where in solutions they use memset to initialize the 2d array with zero. How should fix this.

4

Sorry initialize with -1*

5

Check the method three, here also whole array is initialized with -1.

I m still noob, please be patient and help❣️

6

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.
2 Likes
7

Got it. Thanku so much. U helped me last time also. Thanku so much.

8

#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

9

Please fix this code and share,please.

10

Sir, do respond please.

11

Please format your code - the forum software has mangled it and it won’t compile! :slight_smile:

12

ok will do that thanks.

13 
#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;
}
1 Like
14

now please fix this code and tell me what was wrong there?

15

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;
}

16

since the function is non void therefore you need to make sure that it has an output to print.