【 Backpack problem series 】 a classic backpack problem

This series is based on the study of Gongshui Sanye’s big wechat public number – backpack problem after sorting out, if there is any violation, please inform us

[Blog link]

A path to learning at 🐔

Classic backpack problem

[B].

There are values. Length items and a backpack with a capacity of N. There is one and only one of each item. The weights are **weights[I]**, and the values are **values[I]**. Solve which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity, and the total value of the maximum. Example 1: Input: V = 4, values = [4,2,3], weights = [4,2,3] Output: 4 Explanation: Select only the first item to maximize the value. Example 2: input: V = 5, values = [4,2,3], weights = [4,2,3] output: 5 explanation: do not select the first item, select the second and third items to maximize the value.Copy the code

[D].

• So when we’re dealing with dp problems and we can’t think of the DP equation directly at first, we can think of DFS recursion to determine the recursive equation

• Int DFS (int n,int I,int [] values, int[] weights)

• N (current capacity), I (current item)

• Therefore, the DP equation can be generated by two variable parameters

• Dp [I][j] represents the highest value obtained for I items at maximum weight J before use

• When I = 0, we need to initialize dp array dp[0][j]

• The derivation of dynamic equation can be analyzed according to the following ideas

• Face value whether I, need to decide to take * * (dp [I] [j – weight [I]] + val [I]) * * or don’t take (dp) [j] [I – 1] whose value is higher

• dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weights[i]] + values[i])
  Copy the code

public int getMaxValue(int[] value, int[] weights, int n) {
            int[][] dp = new int[value.length][n + 1];
            // Boundary conditions
            for (int i = 0; i < n; i++) {
                dp[0][i] = (weights[0] <= i) ? value[0] : 0;
            }
            for (int i = 1; i < value.length; i++) {
                int val = value[i];
                for (int j = 1; j <= n; j++) {
                    if (j >= weights[i]) {
                        // Select and deselect the maximum value of the current item
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + val); }}}return dp[value.length - 1][n];
        }
Copy the code

Time complexity O(N*C) N represents the number of items and C represents the maximum weight

Optimization 1: a combination of scrolling arrays and dynamic programming optimizes storage space

• According to the above recursive equation, it can be seen that DP [I][j] is only related to DP [i-1][j]. Such a dynamic programming problem can be solved by rolling the array dp equation
• Define **dp[2][j]** to store the previous bit’s maximum value solution and the current bit’s maximum value solution
• How do we traverse two elements we can translate traverse by parity

 public int getMaxValue(int[] values, int[] weights, int n) {
            int[][] dp = new int[2][n + 1];
            for (int i = 0; i < n; i++) {
                dp[0][i] = (weights[0] <= i) ? values[0] : 0;
            }
            for (int i = 1; i < values.length; i++) {
                for (int j = 0; j <= n; j++) {
                    // Do not select the current item
                    int tempF = dp[(i - 1) & 1][j];
                    // Select the current item
                    int tempT = j >= weights[i] ? dp[(i - 1) & 1][j - weights[i]] + values[i] : 0;
                    dp[i & 1][j] = Math.max(tempF, tempT); }}return dp[(values.length - 1) & 1][n];
        }
Copy the code

Time complexity O(N*C) N represents the number of items and C represents the maximum weight

Optimization two: clear dependence, space optimization again

• Based on the above optimization, you can see that the current maximum value is related to only two determined values
• Is the dp [I] [j] only dp [j] and [I – 1] * * dp [I] [j – weights [I]] * * two values
• 

public int getMaxValue(int[] values, int[] weights, int n) {
            int[] dp = new int[n + 1];
            for (int i = 0; i < values.length; i++) {
                for (int j = n; j >= weights[i]; j--) {
                    // do not select this item
                    int x = dp[j];
                    // Select this item
                    inty = dp[j - weights[i]] + values[i]; dp[j] = Math.max(x, y); }}return dp[n];
        }
Copy the code