# Geeksforgeeks Solution For " 0 - 1 Knapsack Problem "

GeeksforGeeks Solution For Hard Domain .Below You Can Find The Solution Of  School Basic ,Easy ,Medium . Or Hackerrank Solution You Can Also Direct Submit Your Solution to Geeksforgeeks Same Problem .You Need to login then you can submit you answers

Problem :- 0 - 1 Knapsack Problem

Solution :-

#include<iostream>
using namespace std;
int max(int ,int ) ;
int Knapsack_Problem(int [],int [],int ,int ) ;
int main()
{
int t,no,w,val[100],weight[100],i ;
cin>>t ;
while(t--)
{
cin>>no ;
cin>>w ;

for(i=0;i<no;i++)
cin>>val[i] ;

for(i=0;i<no;i++)
cin>>weight[i] ;

no=Knapsack_Problem(val,weight,no,w) ;
cout<<no<<endl ;
}
return 0;
}

int Knapsack_Problem(int val[],int weight[],int no,int w)
{
int i,j ;
int mat[no+1][w+1]={0} ;

for(i=0;i<=no;i++)
mat[i][0]=0 ;

for(i=0;i<=w;i++)
mat[0][i]=0 ;

for(i=1;i<=no;i++)
{
for(j=1;j<=w;j++)
{
if(j>=weight[i-1])
{
mat[i][j]=max(mat[i-1][j],val[i-1]+mat[i-1][j-weight[i-1]]) ;
}
else if(i>1)
mat[i][j]=mat[i-1][j] ;
}
}
return mat[no][w] ;
}

int max(int a,int b)
{
return a>b?a:b ;
}

Output:-