0/1 Knapsack Example (using RECURSION)-C++

 

#include<bits/stdc++.h>

using namespace std;

int knapsack(int W1[],int V1[],int W,int n)

{

if(W==0 || n==0) return 0;

if(W1[n-1]<=W) return V1[n-1]+knapsack(W1,V1,W-W1[n-1],n-1);

else if(W1[n-1]>W) return knapsack(W1,V1,W,n-1);

}

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

//freopen("input.txt","r",stdin);

int W1[1000],V1[1000];

int W,t,j;

cin>>t;

for(j=1;j<=t;j++)

{

int n;

cin>>n>>W;

int i;

for(i=0;i<n;i++)

{

cin>>W1[i]>>V1[i];

}

cout<<"Case "<<j<<": "<<knapsack(W1,V1,W,n)<<endl;

}

return 0;

}