KnapSack.java

class KnapSackProblem {
    int[] vals;
    int[] weights;

    KnapSackProblem(int[] v, int[] w) { vals = v; weights = w; }

    public int solve_naive(int W) {
        return solve_recnaive(vals.length - 1, W);
    }

    private int solve_recnaive(int i, int W) {
        if(i < 0)
            return 0;
        else if(weights[i] > W)
            return solve_recnaive(i-1, W);
        else
            return Math.max(vals[i] + solve_recnaive(i-1, W - weights[i]), solve_recnaive(i-1, W));
    }

    public int solve_DP(int W) {
        int[][] r =  new int[vals.length][W + 1];

        for (int i=0; i < vals.length; i++) {
            for(int w=0; w <= W; w++) {
                if(i == 0) {
                    if (weights[i] > w)
                        r[i][w] = 0;
                    else
                        r[i][w] = vals[i];
                }
                else if (weights[i] > w)
                    r[i][w] = r[i-1][w];
                else
                    r[i][w] = Math.max(vals[i] + r[i-1][w - weights[i]], r[i-1][w]);
            }
        }

        int w = W;
        int i = vals.length-1;
        while (w > 0 && i >=0) {
            if ((i == 0 && weights[0] <= w) || (i> 0 && r[i][w] != r[i-1][w])) {
                System.out.println("Knapsack contains item " + (i) + " (val=" + vals[i] + ", w=" + weights[i]  + ")");
                w -= weights[i];
            }
            i--;
        }

        System.out.println("Weight of knapsack is " +  (W - w));

        return r[vals.length-1][W];
    }
}

public class KnapSack {
    public static void main(String[] args) {
        int cap = 11;
        KnapSackProblem p = new KnapSackProblem(new int[] {20, 5, 10, 40, 15, 25}, new int[] {1, 2, 3, 8, 7, 4});
        System.out.println("(naive) Total is " + p.solve_naive(cap));
        System.out.println("Total is " + p.solve_DP(cap));
    }
}