DP 的四个步骤
- 刻画一个最优解的结构特征。
- 递归地定义最优解的值。
- 计算最优解的值,通常采纳自底向上法。
- 利用计算出的信息结构一个最优解。
前三步是 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…
参考书目:算法导论