I didn't understand the multiple knapsack problems I encountered when learning dynamic programming, so I started to record my understanding from the simplest 01 knapsack.

1. What is the 01 knapsack problem

There is a knapsack with a capacity of a known number (V). You want to use this knapsack to hold a known number (n) of different objects, each of which has a known size (w) and a known value (v). Each object can only hold one. Find out which objects the backpack can hold to maximize its value.

Because each object has only two states (1) and not (0), the problem is called 01 knapsack.

1. 01 How to calculate the knapsack problem

The code is as follows, v is the value array of the several items, and w is the size array of the several items.

private static int bestValue(int[] v,int[] w,int V){
        int n = v.length;
        int [][] f = new int[V+1][n+1];//Create a matrix, the abscissa is V+1 is the capacity, the ordinate is n+1 is the area occupied by the item, and the content of the coordinates is the highest value placement method
        //Fill boundary rows and columns, in this case, both rows and columns are 0
        for (int i = 0; i < n; i++) {
            f[0][i]=0;
        }
        for (int i = 0; i < V; i++) {
            f[i][0]=0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if(j < w[i-1]){//If the capacity of the backpack is less than the area occupied by the item, take the previous maximum value
                    f[j][i] = f[j][i-1];
                }else {//If it is greater than, calculate the maximum value of putting in and not putting in as the current maximum value
                    f[j][i] = Math.max(f[j][i-1],f[j-w[i-1]][i-1]+v[i-1]);
                }
            }
        }

        return f[V][n];
    }

The steps are:

1. Create a two-dimensional array int [][] f, the abscissa is the backpack capacity V, and the ordinate is the number n of items (note: n is not the nth). Equivalent to the following table, the size cn and value vn of the nth item are inside the boast. The value corresponding to the horizontal and vertical coordinates is the maximum value of the current capacity and the number of items.

1. In this problem, when there are 0 items or the knapsack capacity is 0, the total value must be 0, so set the starting values ​​of rows and columns to 0 when V or n is 0 as shown in the above table (known solution). It is reflected in the code that all values ​​​​of the planes f[i][0] and f[0][i] are set to 0.

1. When the knapsack capacity j and the number of items i are not 0, there are two situations:

1. If the knapsack capacity j is smaller than the size of the i-th item, the knapsack cannot hold the item, then the maximum value at this time is equal to the knapsack capacity j and the maximum value of i-1 items. That is, f[j][i] = f[j][i-1].

1. When the knapsack capacity is greater than the size of the i-th item, the knapsack can hold the item. Then it is necessary to compare the maximum value when the item is installed and when the item is not installed. This maximum value is the maximum value when the backpack capacity is j and the number of items is i.

Finally, the value traversed to the last cell of the table is f[V][n], which is the required maximum value.

1. The embodiment of dynamic programming thought in 01 knapsack problem

The core idea of ​​dynamic programming:

=>A method to solve complex problems by decomposing the original problem into relatively simple sub-problems;

="Store the calculated value to avoid double calculation.

The first thought manifests itself as follows:

Decompose the problem that there are n items and the knapsack capacity is V as,

1. When the last item can be loaded, calculate the value when loading and not loading; when loading, take the value of the knapsack capacity as V-m[n] plus the value of the nth item, both of which are known of. When not installed, take the value of n-1 directly, and this value is also known.

2. Cannot hold the last item. When the item does not exist directly, take the value of n-1, and this value is also known.

The second idea is embodied as follows:

In the 01 knapsack problem, if you use recursive evaluation, you need to enumerate each combination of n different objects in the knapsack V, as follows:

    private static int myDiguiFun(int i,int[] w,int[] v,int V,int countValue,int countV){
        //i, the number of recursions, is also the number of items
        if(i==w.length){
            return countValue;//If the number of recursion reaches the number of items, it means that the exhaustion is over and jump out of the recursion
        }
        //Compare whether this item +countV is greater than the backpack capacity V
       if(countV+w[i]>V){//If it cannot fit, do not take this item and go directly to the next recursion
           return myDiguiFun(i+1,w,v,V,countValue,countV);
       }else {//If you can fit it, you have to consider which is more cost-effective to take this item or not to take this item
           return Math.max(myDiguiFun(i+1,w,v,V,countValue+v[i],countV+v[i]),
                   myDiguiFun(i+1,w,v,V,countValue,countV));
       }
    }

Although the use of recursion in the 01 knapsack problem is also the idea of ​​transforming complex problems into simple sub-problems, recursion does not store the calculated solutions, resulting in a lot of repeated calculations.

In the dynamic programming algorithm, the evaluation of each grid directly refers to the optimal solution of the previous grid without recalculation, so the time complexity is much simpler than that of recursion.