DP/Knapsack/Solution.java
class Solution {

    public int solveKnapsackTopDown(int[] profits, int[] weights, int capacity) {
       
        Integer[][] dp = new Integer[weights.length][capacity + 1];
        return recursiveKnapsack(dp, profits, weights, capacity, 0);
    }

    public int recursiveKnapsack(Integer[][] dp, int[] profits, int[] weights, int capacity, int index) {
        if (capacity == 0 || index >= weights.length) {
            return 0;
        }
        if (dp[index][capacity] != null) {
            return dp[index][capacity];
        }
        int incProfit = 0;
        if (capacity >= weights[index]) {
            incProfit = profits[index] + recursiveKnapsack(dp, profits, weights, capacity - weights[index], index + 1);
        }
        int exProfit = recursiveKnapsack(dp, profits, weights, capacity, index + 1);
        dp[index][capacity] = Math.max(incProfit, exProfit);
        return dp[index][capacity];
    }

    public int solveKnapsackBottomUp(int[] profits, int[] weights, int capacity) {
        int[][] dp = new int[weights.length][capacity + 1];
        // capacity 0 -- total capacity
        // fill col zero of each row as 0 as no weight is selected for that weight
        for (int i = 0; i < weights.length; i++) {
            dp[i][0] = 0;
        }
        // fill the first column with weight of first element
        // only fill if the current weight can be used
        // i.e if the current weight is greater than capacity at that point we cannot
        // use it
        for (int i = 0; i <= capacity; i++) {
            if (weights[0] <= i) {
                dp[0][i] = weights[0];
            }
        }
        // now that dp is setup
        // go to each item, consider profit when it is selected and previous can be
        // selected
        // consider when it is not selected and previous is selected
        for (int i = 1; i < weights.length; i++) {
            // for each capacity
            for (int j = 1; j <= capacity; j++) {
                int incProfit = 0, excProfit = 0;
                // if current weight can be used include it
                // for each current weight is 2 , then 0, 1 capacities cannot be filled by us
                // so only calculate the exlcuded values, which max of previous row
                if (weights[i] <= j) {
                    incProfit = profits[i] + dp[i - 1][j - weights[i]];
                }
                // what is the max profit if current weight is excludes?
                // ans : the profit generated by previous objects at current capcaity
                excProfit = dp[i - 1][j];
                dp[i][j] = Math.max(incProfit, excProfit);
            }
        }
        return dp[weights.length - 1][capacity];
    }

    public int solveKnapsackBottomUpMem(int[] profits, int[] weights, int capacity) {
        // init dp for only 2 rows
        int[][] dp = new int[2][capacity + 1];
        dp[0][0] = 0;
        dp[1][0] = 0;
        for (int i = 1; i <= capacity; i++) {
            if (weights[0] <= i) {
                dp[0][i] = weights[0];
            }
        }
        // the values of previous row is only needed to calculate the current row
        // so if even row,, fetch values from previous row %2 , and store it in current
        // row
        // vice versa
        for (int i = 1; i < weights.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                int incProfit = 0, excProfit = 0;
                if (weights[i] <= j) {
                    incProfit = profits[i] + dp[(i - 1) % 2][j - weights[i]];
                }
                excProfit = dp[(i - 1) % 2][j];
                dp[i % 2][j] = Math.max(incProfit, excProfit);
            }
        }
        return dp[(weights.length - 1) % 2][capacity];
    }

    public static void main(String[] args) {
        Solution ks = new Solution();
        int[] profits = { 1, 6, 10, 16 };
        int[] weights = { 1, 2, 3, 5 };
        int maxProfit = ks.solveKnapsackTopDown(profits, weights, 7);
        System.out.println("Total knapsack profit ---> " + maxProfit);
        maxProfit = ks.solveKnapsackTopDown(profits, weights, 6);
        System.out.println("Total knapsack profit ---> " + maxProfit);

        maxProfit = ks.solveKnapsackBottomUp(profits, weights, 7);
        System.out.println("Total knapsack profitrec ---> " + maxProfit);
        maxProfit = ks.solveKnapsackBottomUp(profits, weights, 6);
        System.out.println("Total knapsack profitrec ---> " + maxProfit);

        maxProfit = ks.solveKnapsackBottomUpMem(profits, weights, 7);
        System.out.println("Total knapsack profitrec memory efficient ---> " + maxProfit);
        maxProfit = ks.solveKnapsackBottomUpMem(profits, weights, 6);
        System.out.println("Total knapsack profitrec memory efficient ---> " + maxProfit);

    }
}
