package com.thealgorithms.dynamicprogramming;

// Here is the top-down approach of
// dynamic programming

public class MemoizationTechniqueKnapsack {

    // A utility function that returns
    // maximum of two integers
    static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // Returns the value of maximum profit
    static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) {
        // Base condition
        if (n == 0 || W == 0) {
            return 0;
        }

        if (dp[n][W] != -1) {
            return dp[n][W];
        }

        if (
            wt[n - 1] > W
        ) { // stack in table before return // Store the value of function call
            return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);
        } else { // Return value of table after storing
            return (
                dp[n][W] =
                    max(
                        (
                            val[n - 1] +
                            knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)
                        ),
                        knapSackRec(W, wt, val, n - 1, dp)
                    )
            );
        }
    }

    static int knapSack(int W, int wt[], int val[], int N) {
        // Declare the table dynamically
        int dp[][] = new int[N + 1][W + 1];

        // Loop to initially filled the
        // table with -1
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < W + 1; j++) {
                dp[i][j] = -1;
            }
        }

        return knapSackRec(W, wt, val, N, dp);
    }

    // Driver Code
    public static void main(String[] args) {
        int val[] = { 60, 100, 120 };
        int wt[] = { 10, 20, 30 };

        int W = 50;
        int N = val.length;

        System.out.println(knapSack(W, wt, val, N));
    }
}