import java.util.*;
import java.lang.*;
import java.io.*;
 
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);
    }
}
 

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUgewogICAgcHVibGljIHN0YXRpYyBpbnQga25hcHNhY2soaW50W10gd2VpZ2h0cywgaW50W10gdmFsdWVzLCBpbnQgaW5kZXgsIGludCBjYXBhY2l0eSkgewogICAgICAgIGlmIChpbmRleCA9PSAwKSB7CiAgICAgICAgICAgIGlmICh3ZWlnaHRzWzBdIDw9IGNhcGFjaXR5KSByZXR1cm4gdmFsdWVzWzBdOwogICAgICAgICAgICBlbHNlIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBpbnQgbm90VGFrZSA9IGtuYXBzYWNrKHdlaWdodHMsIHZhbHVlcywgaW5kZXggLSAxLCBjYXBhY2l0eSk7CiAgICAgICAgaW50IHRha2UgPSAwOwogICAgICAgIGlmICh3ZWlnaHRzW2luZGV4XSA8PSBjYXBhY2l0eSkgewogICAgICAgICAgICB0YWtlID0gdmFsdWVzW2luZGV4XSArIGtuYXBzYWNrKHdlaWdodHMsIHZhbHVlcywgaW5kZXggLSAxLCBjYXBhY2l0eSAtIHdlaWdodHNbaW5kZXhdKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIE1hdGgubWF4KHRha2UsIG5vdFRha2UpOwogICAgfQogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludFtdIHdlaWdodHMgPSB7MTAwLCA3MCwgNTAsIDEwfTsKICAgICAgICBpbnRbXSB2YWx1ZXMgPSB7MTAsNCw2LDEyfTsKICAgICAgICBpbnQgY2FwYWNpdHkgPSA4OwogICAgICAgIGludCBuID0gd2VpZ2h0cy5sZW5ndGg7CiAgICAgICAgaW50IG1heFByb2ZpdCA9IGtuYXBzYWNrKHdlaWdodHMsIHZhbHVlcywgbiAtIDEsIGNhcGFjaXR5KTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk1heGltdW0gUHJvZml0ID0gIiArIG1heFByb2ZpdCk7CiAgICB9Cn0K