关于算法:算法DP之钢条切割问题

DP 的四个步骤

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值。
3. 计算最优解的值，通常采纳自底向上法。
4. 利用计算出的信息结构一个最优解。

前三步是 DP 求解的根底。若仅须要一个最优解的值，而非解自身，可疏忽第四步。若需第四步，有时需在执行第 3 步的过程中保护一些额定的信息，以便结构一个最优解。

钢条切割例子

场景：把长钢条切割为短钢条发售。切割工序自身无老本。求最佳切割计划。

假设：发售一段长度为 i 英寸的钢条的价格为 Pi(i = 1, 2, …,) 单位:$，钢条长度均为整英寸。下图为价格表。

问题形容：给定一段长度为 n 英寸的钢条和一个价格表，求切割计划，使销售收益 Rn 最大。注：若长度为 n 英寸的钢条的价格 Pn 足够大，最优解可能就是齐全不须要切割。

思考长度为 4 的状况，下图给出了 4 英寸钢条的所有切割计划。

切成两段各长 2 英寸的钢条，将产生 P2 + P2 = 5 + 5 = 10 的收益，为最优解。

长度为 n 英寸的钢条共有 2^(n-1) 种不同切割计划，因为在间隔钢条左端 i (i=1, 2, … , n-1) 英寸处，总是能够抉择切割或者不切割。用一般的加法符号示意切割计划，因而 7 =2+2+ 3 示意将长度为 7 的钢条切割为 3 段：2 英寸，2 英寸，3 英寸。

若一个最优解将钢条切割为 k 段（1≤k≤n），那么最优切割计划 n = i1 + i2 + … + ik.

将钢条切割为长度别离为 i1, i2, … , ik 的小段，失去的最大收益为 Rn = Pi1 + Pi2+…+Pik

对于下面表格的价格样例，能够察看所有最优收益值 Ri (i: 1~10) 以及最优计划：

长度为 1：切割计划 1 =1（无切割）。最大收益 R1 = 1

长度为 2：切割计划 2 =2（收益 5），1+1=2（收益 2）。最大收益 R2 = 5

长度为 3：切割计划 3 =3（收益 8），1+2=3（收益 6），2+1=3（收益 6）。最大收益 8

长度为 4：切割计划 4 =4（收益 9），1+3=4（收益 9），2+2=4（收益 10），3+1=4（收益 9），1+1+2=4（收益 7），1+2+1=4（收益 7），2+1+1=4（收益 7），1+1+1+1=4（收益 4）。最大收益 10

长度为 5：切割计划 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），其余是后面的排列。最大收益 13

顺次求出。。。

更个别的，对于 Rn(n≥1)，能够用更短的钢条的最优切割收益来形容它：

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

• 第一个参数 Pn 对应不切割，间接发售长度为 n 的计划。
• 其余 n - 1 个参数对应 n - 1 种计划。对每个 i =1,2,….,n-1，将钢条切割为长度为 i 和 n - i 的两段，接着求解这两段的最优切割收益 Ri 和 Rn-i;(每种计划的最优收益为两段的最优收益之和)。
• 因为无奈预知哪种计划会取得最优收益，必须考查所有可能的 i，选取其中收益最大者。若不切割时收益最大，当然抉择不切割。

留神到：

• 为了求解规模为 n 的原问题，先求解子问题（子问题模式齐全一样，但规模更小）。
• 即首次实现切割后，将两段钢条看成两个独立的钢条切割问题实例。
• 通过组合两个相干子问题的最优解，并在所有可能的两段切割计划中获取收益最大者，形成原问题的最优解。

称钢条切割问题满足最优子结构性质：

问题的最优解由相干子问题的最优解组合而成，而这些子问题能够独立求解。

除上述解法，问题可化简为一种类似的递归：从右边切割下长度为 i 的一段，只对左边剩下的长度为 n-i 的一段进行持续切割（递归求解），对右边一段则不再进行切割。

即问题合成的形式为：将长度为 n 的钢条合成为右边开始一段，以及残余局部持续合成的后果。（这样，不做任何切割的计划能够形容为：第一段长度为 n，收益为 Pn，残余局部长度为 0，对应收益为 R0 = 0）。于是失去下面公式的简化版本：

在此公式中，原问题的最优解只蕴含一个相干子问题（右端残余局部的解），而不是两个。

自顶向下递归实现的伪代码：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 

该过程以价格数组 p[1…n] 和整数 n 为输出，返回长度为 n 的钢条的最大收益。

若 n =0，不可能有任何收益，所以第二行返回 0.

第 3 即将最大收益初始化为负无穷，以便第 4 第 5 行的 for 循环能正确计算。

带备忘的自顶向下法（top-down with memorization）

• 此办法依然依照天然的递归模式编写过程，然而过程会保留每个子问题的解（通常保留在一个数组或散列表中）。

• 当须要一个子问题的解时，过程首先查看是否曾经保留过此解，

  • 如果是，则间接返回保留的值，从而节俭了计算工夫；
  • 否则，依照通常形式计算这个子问题。

JAVA 实现：

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;
}

自底向上法（bottom-up method）

• 该办法个别须要失当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。
• 因此能够将子问题按规模排序，按由小到大的程序进行求解。
• 当求解某个子问题时，所依赖的那些更小的子问题都曾经求解结束，后果曾经保留。
• 每个子问题只求解一次，当求解它时（也是第一次遇到它），所有前提子问题都曾经求解实现。

两种办法失去的算法具备雷同的渐进运行工夫，

• 仅有的差别是在某些非凡状况下，自顶向下办法并未真正递归地考查所有可能的子问题。
• 因为没有频繁的递归调用开销，自底向上的复杂度函数通常具备更小的系数。

JAVA 实现：

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];
}

参考文章：https://segmentfault.com/a/11…
参考书目：算法导论