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);
    }
}
 

aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgSWRlb25lIHsKICAgIHB1YmxpYyBzdGF0aWMgaW50IGtuYXBzYWNrKGludFtdIHdlaWdodHMsIGludFtdIHZhbHVlcywgaW50IGluZGV4LCBpbnQgY2FwYWNpdHkpIHsKICAgICAgICBpZiAoaW5kZXggPT0gMCkgewogICAgICAgICAgICBpZiAod2VpZ2h0c1swXSA8PSBjYXBhY2l0eSkgcmV0dXJuIHZhbHVlc1swXTsKICAgICAgICAgICAgZWxzZSByZXR1cm4gMDsKICAgICAgICB9CiAgICAgICAgaW50IG5vdFRha2UgPSBrbmFwc2Fjayh3ZWlnaHRzLCB2YWx1ZXMsIGluZGV4IC0gMSwgY2FwYWNpdHkpOwogICAgICAgIGludCB0YWtlID0gMDsKICAgICAgICBpZiAod2VpZ2h0c1tpbmRleF0gPD0gY2FwYWNpdHkpIHsKICAgICAgICAgICAgdGFrZSA9IHZhbHVlc1tpbmRleF0gKyBrbmFwc2Fjayh3ZWlnaHRzLCB2YWx1ZXMsIGluZGV4IC0gMSwgY2FwYWNpdHkgLSB3ZWlnaHRzW2luZGV4XSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBNYXRoLm1heCh0YWtlLCBub3RUYWtlKTsKICAgIH0KICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSB3ZWlnaHRzID0gezEwMCwgNzAsIDUwLCAxMH07CiAgICAgICAgaW50W10gdmFsdWVzID0gezEwLDQsNiwxMn07CiAgICAgICAgaW50IGNhcGFjaXR5ID0gODsKICAgICAgICBpbnQgbiA9IHdlaWdodHMubGVuZ3RoOwogICAgICAgIGludCBtYXhQcm9maXQgPSBrbmFwc2Fjayh3ZWlnaHRzLCB2YWx1ZXMsIG4gLSAxLCBjYXBhY2l0eSk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJNYXhpbXVtIFByb2ZpdCA9ICIgKyBtYXhQcm9maXQpOwogICAgfQp9Cg==