knapsack.java

import java.util.Scanner;

public class knapsack{
    public static void main(String args[]){
        int n;
        Scanner scn = new Scanner(System.in);
        n = scn.nextInt();

        int[] weight = new int[n];  
        inputArr(weight, scn);
        int[] value = new int[n];
        inputArr(value, scn);
        int maxCapacity = scn.nextInt();

        int ans = maxProfit(weight, value, maxCapacity, 0);
        System.out.println(ans);
    } 

    public static void inputArr(int[] arr, Scanner scn){
        for(int i = 0; i < arr.length; ++i){
            arr[i] = scn.nextInt();
        }
    }

    public static int maxProfit(int[] weight, int[] value, int maxCapacity, int beIdx){
        if (beIdx == weight.length){
            // No items to pick
            return 0;
        }

        int profitByExcludingCurItem = maxProfit(weight, value, maxCapacity, beIdx + 1);
        int profitByIncludingCurItem = 0;
        if (weight[beIdx] <= maxCapacity){
            // item at beIdx can be picked
            profitByIncludingCurItem += value[beIdx];
            int remCapacity = maxCapacity - weight[beIdx];
            profitByIncludingCurItem += maxProfit(weight, value, remCapacity, beIdx + 1);
        }
        return Math.max(profitByExcludingCurItem, profitByIncludingCurItem);        
    }
}