1. Introduction

1. The core idea of Dynamic Programming algorithm is to divide big problems into small problems to solve, so as to obtain the optimal solution step by step

2. Dynamic algorithm is similar to divide-and-conquer algorithm, its basic idea is to decompose the large problem to be solved into several sub-problems, solve the sub-problems first, and then get the solution of the source problem from the solution of these sub-problems

3. Different from the divide-and-conquer algorithm, the problems suitable for solving by dynamic programming are usually not independent of each other after decomposition (that is, the solution of the next sub-stage is based on the solution of the previous sub-stage and further solution is carried out).

4. Dynamic programming can be advanced step by step by filling in the form to get the optimal solution

2. Practice-backpack problem

2.1 the problem

Backpack problem: There is a backpack with a capacity of 4 pounds and the following items are available

Requirements:

1. Reach the target for the maximum value of the backpack loaded, and the weight does not exceed

2. Loading items cannot be repeated

2.2 train of thought

1. Backpack problem is mainly a backpack of a given capacity, a number of items with a certain value and weight, how to choose items into the backpack to maximize the value of the items. Which is divided into 01 backpack and full backpack (full backpack refers to each item has unlimited availability)

2. The problem here belongs to 01 knapsack, that is, each item can put a maximum of one, and unlimited knapsack can transform 01 knapsack.

3. The main idea of the algorithm: using dynamic programming to solve. For the ith item of each traverse, according to W [I] and V [I], it is determined whether the item needs to be put into the backpack. For a given n items. Let v[I] and W [I] be the value and weight of the ith item respectively, and C be the capacity of the backpack. Let v[I] [j] represent the maximum value of the first I items that can fit into a backpack of capacity J. Then we have the following results:

(1)v[i] [0] = v[0] [j] = 0; // fill in the first row and column with 0

(2) when w[I] > j, v[I] [j] = v[i-1] [j] // When the capacity of the new goods to be added is greater than the current backpack capacity, directly use the loading strategy of the previous cell;

(3) when the [I] > = j w, v [I] [j] = Max {v [j], [I – 1] v [I] + v [I – 1] [I]] [j – w}

// When the capacity of the new item to be added is less than or equal to that of the current backpack

// How to load

V [i-1] [j], is the maximum load of the previous cell

V [I]: indicates the current value of the commodity

V [i-1] [j-w[I]], load i-1 goods to the maximum value of the remaining space J-w [I]

When [I] > = j w, v [I] [j] = Max {v [j], [I – 1] v [I] + v [I – 1] [I]] [j – w}

2.3 code

public class KnapsackProblem {

    public static void main(String[] args) {
        // The weight of the item
        int[] w = {1.4.3};
        Val [I] = val[I] = val[I]
        int[] val = {1500.3000.2000};
        // The capacity of the backpack
        int m = 4;
        // The number of items
        int n = val.length;
        // Create a two-dimensional array
        //v[I][j] represents the maximum value of the first I items that can fit into a backpack of capacity J
        int[][] v = new int[n+1][m + 1];
        // To keep track of the items put in, we make a two-dimensional array
        int[][] path = new int[n + 1][m + 1];

        // Initialize the first row and column, which are not handled in this program, because the default is 0
        for (int i = 0; i < v.length; i++) {
            // Set the first column to 0
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            // Set the first line to 0
            v[0][i] = 0;
        }

        // Dynamically plan the processing according to the previous formula
        // The first line I starts at 1
        for (int i = 1; i < v.length; i++) {
            // do not deal with the first column, j starts at 1
            for (int j = 1; j < v[0].length; j++) {
                / / formula
                // Because we start from 1, so the original formula w[i-1]
                if (w[i - 1] > j) {
                    v[i][j] = v[i-1][j];
                } else {
                    / / that
                    // Since our I starts at 1, the formula needs to be adjusted to
                    //v[i][j] = Math.max(v[i-1][j], val[i - 1] + v[i-1][j- w[i-1]])
                    // In order to record the goods stored in the backpack, we can not directly use the above formula, we need to use if-else to express the formula
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j-w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j-w[i - 1]].// Record the current situation to path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i-1][j]; }}}}// Print v to see what's going on
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.println(v[i][j] + "");
            }
            System.out.println();
        }

        System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = =");

        // Output the last item we put in
        // Iterate through the path, so that the output will get all the places put in, in fact we only need the last place
// for (int i = 0; i < path.length; i++) {
// for (int j = 0; j < path[i].length; j++) {
// if (path[i][j] == 1) {
// system.out. printf(" put %d item into backpack \n", I);
/ /}
/ /}
/ /}

        / / think
        // Maximum index of rows
        int i = path.length - 1;
        // The maximum index of the column
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.printf("The %d item is placed in the backpack \n", i);
                //w[i - 1]
                j = w[i - 1]; } i --; }}}Copy the code