import java.util.*;

class Ideone {
    public static int knapsack(int[] weights, int[] values, int index, int capacity) {
        if (index == 0) {
            if (weights[0] <= capacity) return values[0];
            else return 0;
        }
        int notTake = knapsack(weights, values, index - 1, capacity);
        int take = 0;
        if (weights[index] <= capacity) {
            take = values[index] + knapsack(weights, values, index - 1, capacity - weights[index]);
        }
        return Math.max(take, notTake);
    }
    public static void main(String[] args) {
        int[] weights = {100, 70, 50, 10};
        int[] values = {10,4,6,12};
        int capacity = 8;
        int n = weights.length;
        int maxProfit = knapsack(weights, values, n - 1, capacity);
        System.out.println("Maximum Profit = " + maxProfit);
    }
}