The four steps of DP

  1. To characterize the structural characteristics of an optimal solution.
  2. Recursively define the value of the optimal solution.
  3. Calculate the value of the optimal solution, usually using the bottom-up method.
  4. Using the calculated information, an optimal solution is constructed.

The first three steps are the basis for solving DP. If you only need the value of an optimal solution, but not the solution itself, you can ignore Step 4. If a fourth step is required, it is sometimes necessary to maintain some additional information during the execution of step 3 in order to construct an optimal solution.

Examples of steel bar cutting

Scene: Long steel bars are cut into short ones and sold. The cutting process itself has no cost. Seek the best cutting scheme.

Assume that a length of steel bar I inches is sold at a price of Pi(I = 1, 2… Unit :$. The length of steel bar is all inch. Below is the price list.

Problem Description: Given a section of steel bar with a length of N inches and a price list, find a cutting scheme to maximize sales revenue RN. Note: If the price PN for a length of n “steel bar is large enough, the optimal solution may be no cutting at all.

With a length of 4, the following figure shows all the cutting schemes for a 4-inch steel bar.

Cutting two steel bars of 2 inches each will produce a yield of P2 + P2 = 5 + 5 = 10, which is the optimal solution.

There are 2^(n-1) different cutting methods for n “length steel bars, because the distance between the left end of the steel bar I (I =1, 2… At n-1) inches, you always have the option to cut or not cut. The ordinary addition symbol is used to indicate the cutting scheme, so 7=2+2+3 means that the steel bar of length 7 is cut into three sections: 2 inches, 2 inches, 3 inches.

If an optimal solution cuts the steel bar into k segments (1≤k≤n), then the optimal cutting scheme n = I1 + I2 +… + ik.

Cut the steel bar into lengths of I1, I2… , the maximum return obtained is Rn = Pi1 + Pi2+… +Pik

For the price sample in the table above, all the optimal profit values Ri (I: 1~10) and the optimal plan can be observed:

Length 1: Cutting scheme 1=1 (no cutting). Maximum return R1 = 1

Length is 2: cut scheme 2=2 (benefit 5), 1+1=2 (benefit 2). Maximum return R2 is equal to 5

The length is 3: cutting scheme 3=3 (benefit 8), 1+2=3 (benefit 6), and 2+1=3 (benefit 6). Maximum revenue 8

The length is 4: cutting scheme 4=4 (revenue 9), 1+3=4 (revenue 9), 2+2=4 (revenue 10), 3+1=4 (revenue 9), 1+1+2=4 (revenue 7), 2+1+1=4 (revenue 7), 1+1+1=4 (revenue 4). Maximum revenue 10

Length is 5: Cut scheme 5=5 (10), 1+4=5 (10), 2+3=5 (13), 1+1+3=5 (10), 2+2+1=5 (11), 1+1+1+1+1=5 (5), others are the previous arrangement. Maximum revenue 13

Find out… in turn.

More generally, for Rn(n≥1), it can be described in terms of the optimal cutting gain of a shorter steel bar:

Rn = Max (Pn, R1+ rn-1, R2 + rn-2… , Rn-1 + R1)

  • The first parameter Pn corresponds to the scheme of length n without cutting.
  • The other n-1 parameters correspond to n-1 scenarios. For each I = 1, 2,… .,n-1, the steel bar is cut into two sections of length I and n-i, and then the optimal cutting income Ri and Rn-i of these two sections are solved; (The optimal return of each scheme is the sum of the optimal return of the two segments).
  • Since it is impossible to predict which scheme will yield the best return, we must examine all possible options and select the one with the greatest return. If you do not cut when the maximum benefit, of course, choose not to cut.

Notice:

  • To solve the original problem of size n, we first solve the subproblem (of exactly the same form, but of a smaller scale).
  • In other words, two sections of steel bars are regarded as two independent examples of steel bar cutting after the first cutting.
  • The optimal solution of the original problem is formed by combining the optimal solution of two related subproblems and obtaining the maximum benefit from all possible two-segment cutting schemes.

It is said that the steel bar cutting problem satisfies the optimal substructure property:

The optimal solution of the problem is composed of the optimal solutions of the related subproblems, which can be solved independently.

In addition to the above solution, the problem can be reduced to a similar recursion: cut the length I from the left, and continue to cut the length n-i from the right (recursive solution), and do not cut the left segment.

That is, the problem is decomposed as follows: the steel bar of length n is decomposed into the left beginning section, and the remaining part continues to be decomposed. (Thus, the scheme without any cutting can be described as: the length of the first segment is n, and the benefit is Pn; the length of the remaining segment is 0, and the corresponding benefit is R0 = 0). This leads to a simplified version of the above formula:

In this formula, the optimal solution to the original problem consists of only one related subproblem (the solution of the remaining part at the right end), not two.

Pseudocode for top-down recursive implementation: Cut-rod (p, n)

Cut-rod (p, n) 1 if n==0 2 return 0 3 q = -∞ 4 for I = 1 to n 5 q = Max (q, p[I] + cut-rod (p, n-i)) 6 return q

This procedure takes the price array p[1…n] and the integer n as inputs, and returns the maximum return for a steel bar of length n.

If n=0, there can be no gain, so the second row returns 0.

Line 3 initializes the maximum payoff to minus infinity so that the for loop on line 4 and 5 calculates correctly.

Top-down with memorization

  • This method still writes the procedure in the natural recursive form, but the procedure saves the solution to each subproblem (usually in an array or hash table).

  • When a solution to a subproblem is needed, the procedure first checks to see if the solution has been saved,

    • If it is, the saved value is returned directly, thus saving computation time;
    • Otherwise, calculate the subproblem in the usual way.

JAVA implementation:

public static void main(String[] args) {
  int[] p = new int[]{1, 5, 8, 9, 10};
  int result = memorizedCutRod(p, 5);
  System.out.println(result);
}
private static int memorizedCutRod(int[] p, int n) {
  int[] r = new int[n + 1];
  Arrays.fill(r, Integer.MIN_VALUE);
  return memorizedCutAux(p, n, r);
}
private static int memorizedCutAux(int[] p, int n, int[] r) {
  if (n == 0) {
    r[n] = 0;
  }
  if (r[n] >= 0) {
    return r[n];
  }
  int q = Integer.MIN_VALUE;
  for (int i = 1; i <= n; i++) {
    q = Math.max(q, p[i - 1] + memorizedCutAux(p, n - i, r));
  }
  r[n] = q;
  return q;
}

The Bottom-up Method

  • This method generally requires the concept of “size” of subproblems to be properly defined so that the solution of any subproblem only depends on the solution of “smaller” subproblems.
  • Therefore, the subproblems can be sorted according to the scale and solved in the order from small to large.
  • When a subproblem is solved, all the smaller subproblems that depend on it have been solved, and the results have been saved.
  • Each subproblem is solved only once, and when it is solved (and is encountered for the first time), all of the premise subproblems have been solved.

The algorithm obtained by the two methods has the same asymptotic running time,

  • The only difference is that in some special cases, the top-down approach does not really recursively examine all possible subproblems.
  • Bottom-up complexity functions typically have smaller coefficients due to the lack of frequent recursive call overhead.

JAVA implementation:

public static void main(String[] args) {
  int[] p = new int[]{1, 5, 8, 9, 10};
  int result1 = bottomUpCutRod(p, 5);
  System.out.println(result1);
}
private static int bottomUpCutRod(int[] p, int n) {
  int[] r = new int[n + 1];
  r[0] = 0;
  for (int i = 1; i <= n; i++) {
    int q = Integer.MIN_VALUE;
    for (int j = 1; j <= i; j++) {
      q = Math.max(q, p[j - 1] + r[i - j]);
    }
    r[i] = q;
  }
  return r[n];
}

References:
https://segmentfault.com/a/11…


Bibliography: Introduction to Algorithms