“This is the 14th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Dynamic programming is a method of solving complex problems. The key idea is to break up a large problem into a set of simpler subproblems, solve each subproblem only once, and store the solution using memory-based data structures. Each subproblem solution is indexed in some way. Usually the value of the input parameter is used for lookups. Therefore, when the same subproblem occurs, it is not necessary to recalculate the solution, but to find the solution previously calculated, so as to save computing time. This idea of storing the solution to the subproblem becomes dynamic programming.

There is a classic explanation of dynamic programming on Quora. How do I explain dynamic programming to a 4-year-old?

On a piece of paper write “1+1+1+1+1+1+1+1 =?

Answer: “Eight!”

On the left hand side, let’s write another 1 plus, which is equal to what?

Answer: “Nine!”

How did you do that so fast?

Answer: “You just added one.”

So you don’t have to recalculate, because you remember eight! Dynamic programming is just a fancy way of saying remember something to save time

Dynamic programming classical problem: 0-1 knapsack problem

Now I need to travel and sort out some items. Each item has two attributes, necessity and weight. The load-bearing capacity of the bag is limited, and the requirement is to load the most needed items as much as possible on the basis of meeting the load-bearing capacity of the bag. Each item can only hold one.

Code examples:

Input: Necessity = [20, 5, 10, 40, 15, 25]\ Weight = [1, 2, 3, 8, 7, 4]\ int W = 10 (W is the load bearing limit of the bag) Necessity of back packing: 60 Necessity = 20 + 40 = 60 Weight = 1 + 8 = 9 < WCopy the code

recursive

Use recursive thinking to solve this problem. Include the current item in the backpack and use the remaining items that are reduced in the backpack capacity. If the capacity becomes negative, it does not return, or it returns negative infinity.

Finally, we return the maximum value we got by including or excluding the current item. The base case for recursion is either no items left, or zero capacity.

Java sample code:

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // Base case: There are no remaining items or the capacity becomes 0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. Put the current item "v[n]" in the backpack and reuse it
        // Remaining item 'n-1' capacity reduced by 'w-w [n]'
 
        int include = v[n] + knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. Remove the current item 'v[n]' from the backpack and reuse it
        // Remaining item 'n-1 '
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // Returns the maximum value obtained by including or excluding the current item
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // Input values, v: necessity, w: weight
        int[] v = { 20.5.10.40.15.25 };
        int[] w = { 1.2.3.8.7.4 };
 
        // Backpack capacity
        int W = 10;
 
        System.out.println("Backpack essential value is" +
                knapsack(v, w, v.length - 1, W)); }} Output: knapsack necessary value is60
Copy the code

The time complexity of the above solution is exponential and takes up space in the call stack.

The above solutions have optimal substructure, that is, the optimal solution can be effectively constructed from the optimal solution of the subproblem. It also has overlapping subproblems, that is, problems can be broken down into subproblems, and each subproblem is repeated several times. To reuse subproblem solutions, we can use dynamic programming in which the subproblem solutions are stored rather than evaluated over and over again.

Dynamic programming (top-down)

Example:

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // Base case: There are no remaining items or the capacity becomes 0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. Put the current item "v[n]" in the backpack and reuse it
        // Remaining item 'n-1' capacity reduced by 'w-w [n]'
        int include = v[n] + knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. Remove the current item 'v[n]' from the backpack and reuse it
        // Remaining item 'n-1'
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // Returns the maximum value obtained by including or excluding the current item
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // Input values, v: necessity, w: weight
        int[] v = { 20.5.10.40.15.25 };
        int[] w = { 1.2.3.8.7.4 };
 
        // Backpack capacity
        int W = 10;
 
        System.out.println("Backpack essential value is" +
                knapsack(v, w, v.length - 1, W)); }} Output: knapsack necessary value is60
Copy the code

The top-down solution above has a time complexity of O(nW) and requires O(nW) additional space, where N is the total number of items in the input and W is the capacity of the backpack.

We can also take a bottom-up approach to the problem. In the bottom-up approach, we solve the smaller subproblems first and then the larger subproblems from there. The following bottom-up method T[I][j] computs for each 1 <= I <= n sum, which is the maximum that can be obtained with 0 <= j <= W for items with weights less than or equal to and using most of the first terms. Use smaller and calculated values.

Dynamic programming (bottom-up)

class Main
{
    public static int knapsack(int[] v, int[] w, int W)
    {
        // 'T[I][j]' stores the maximum weight of the backpack
        // less than or equal to 'j', only the first 'I' term is considered.
        int[][] T = new int[v.length + 1][W + 1];
 
        for (int i = 1; i <= v.length; i++)
        {
            // Consider the ownership weight from 0 to the maximum capacity W
            for (int j = 0; j <= W; j++)
            {
                // If 'j-w[i-1]' is negative, the ith element is not included
                if (w[i-1] > j) {
                    T[i][j] = T[i-1][j];
                }
                else {
                    // Find the maximum we get by exclusion or inclusion
                    / / the first item
                    T[i][j] = Integer.max(T[i-1][j], T[i-1][j-w[i-1]] + v[i-1]); }}}// Return the maximum value (necessary)
        return T[v.length][W];
    }
 
    public static void main(String[] args)
    {
        // Input values, v: necessity, w: weight
        int[] v = { 20.5.10.40.15.25 };
        int[] w = { 1.2.3.8.7.4 };
 
        // Backpack capacity
        int W = 10;
 
        System.out.println("Backpack essential value is"+ knapsack(v, w, W)); }} Output: knapsack necessary value is60

Copy the code

The above bottom-up solution has a time complexity of O(nW) and requires O(nW) additional space, where N is the total number of items in the input and W is the capacity of the backpack.