0/1 Knapsack Problem

/*
  The 0/1 Knapsack Problem solved with dynamic programming.
*/




class Knapsack01 {
    public static void main(String args[]) {
        int[] values = new int[]{ 40,20,60,100 };
        int[] weights = new int[]{ 1, 2, 3, 4 };

        int maxWeight = 5;

        int[][] dpCache = new int[values.length + 1][maxWeight + 1]; // rows => consider items 0...(total items), cols => weights 0...(max weight)
        System.out.println(knapsackBottomUp(values, weights, maxWeight, dpCache)); // 390
        printCache(dpCache);
        newline();

    }

    private static int knapsackBottomUp(int[] values, int[] weights, int maxWeightConstraint, int[][] cache) {

        for (int totalItems = 0; totalItems <= values.length; totalItems++) {
            for (int maxWeight = 0; maxWeight <= maxWeightConstraint; maxWeight++) {
        /*
            1.) Without Item -> Going up 1 row
            2.) With Item -> Go up 1 row & left 'weights[currentItem]' columns
        */
                int currentItem = totalItems - 1;

                if (totalItems == 0 || maxWeight == 0) {
                    cache[totalItems][maxWeight] = 0;
                } else if (weights[currentItem] > maxWeight) {
                    cache[totalItems][maxWeight] = cache[totalItems - 1][maxWeight];
                } else {
                    int withItem = values[currentItem] + cache[totalItems - 1][maxWeight - weights[currentItem]];
                    int withoutItem = cache[totalItems - 1][maxWeight];

                    cache[totalItems][maxWeight] = Math.max(withItem, withoutItem);
                }
            }
        }

        return cache[values.length][maxWeightConstraint];
    }


    private static void printCache(int[][] cache) {
        for (int[] row: cache) {
            for (int col: row) {
                System.out.print(col + " ");
            }
            System.out.println();
        }
    }

    private static void newline() {
        System.out.println();
    }
}