Zero One Knapsack | Recursion

 1. You are given a number n, representing the count of items.

2. You are given n numbers, representing the values of n items.

3. You are given n numbers, representing the weights of n items.

3. You are given a number "cap", which is the capacity of a bag you've.

4. You are required to calculate and print the maximum value that can be created in the bag without 

     overflowing it's capacity.

Note: Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.

Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

A number representing the maximum value that can be created in the bag without overflowing it's capacity

Constraints

1 <= n <= 20

0 <= v1, v2, .. n elements <= 50

0 < w1, w2, .. n elements <= 10

0 < cap <= 10

Sample Input

5

15 14 10 45 30

2 5 1 3 4

7

Sample Output

75

Solution:

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int wt[] = new int[n], val[] = new int[n];

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

            val[i] = sc.nextInt();

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

            wt[i] = sc.nextInt();

        int cap = sc.nextInt();

        

        System.out.println(knapsack(0,n,val,wt,cap));

    }

    

    public static int knapsack(int i,int n,int val[],int wt[],int cap){

        if(i>=n || cap<=0) 

            return 0;

        int taken = 0;

        if(cap-wt[i]>=0)

            taken = knapsack(i+1,n,val,wt,cap-wt[i]) + val[i];

        int notTaken = knapsack(i+1,n,val,wt,cap);

        

        return Math.max(taken, notTaken);

    }

}