动态规划之钢条切割
动态规划简介(算法导论)
动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解，但是不是唯一的最优解，因为可能有多个解都能达到最优值。
我们通常按如下4个步骤来设计一个动态规划算法：
- 刻画一个最优解的结构特征。
- 递归地定义最优解的值。
- 计算最优解的值，通常采用自底向上的方法。
- 利用计算出的信息构造一个最优解。
钢条切割
问题描述
给定一段长度为 nn 英寸的钢条和一个价格表 pi(i=1,2,…,n)pi(i=1,2,…,n)， 求切割钢条方案，使得销售收益 rnrn 最大。
| 长度 ii | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格 pipi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
表1.1 钢条价格样例。每段长度为 ii 英寸的钢条为公司带来 pipi 美元的收益
动态规划求解
长度为 nn 英寸的钢条共有 2n−12n−1 种不同的切割方案。在距离钢条左端 i(i=1,2,…,n−1)i(i=1,2,…,n−1) 英寸处，我们可以选择切割或者不切割。为了方便描述，我们用加法符号表示切割方案，比如7=2+2+3表示将长度为7英寸的钢条切割为三段(长度为2、2、3)。
如果一个最优解将钢条切割 kk 段(1<=k<=n1<=k<=n),那么最有切割方案，可以用如下表示方式
将钢条切割为长度为 i1,i2,…,iki1,i2,…,ik 的小段，得到最大利益表示如下
最优解结构
为了求解规模为 nn 的原问题，我们可以将其分解为规模更小的子问题求解。如果问题的最优解由相关子问题的最优解组合得到，我们则称此问题满足最优子结构。在钢条切割问题上，我们完成钢条首次切割后,可以将两段钢条看成两个独立的钢条切割实例。通过组合两个子问题的最优解，并在所有可能中取收益最大的组合方案得到最优解。
递归定义
将钢条从左边切割长度为 ii 的一段，右边剩下长度为 n−1n−1 ,假定左边钢条不再切割，只需对右边钢条继续切割，使用递归的思想求解。可得到以下递归版本定义
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static long getCutRod(long[] p, int n) {
if (n == 0)
return 0;
long q = Long.MIN_VALUE;
for (int i = 1; i <= n; i++) {
if(i==11){
System.out.println(i);
}
q = Math.max(q, p[i] + getCutRod(p, n - i));
}
return q;
}
|
其中数组p表示价格数组，数组大小为n+1，初始化如下
if(n<=10),数组大小定义为11，初始化如下
p[0] = 0;
p[1] = 1;
p[2] = 5;
p[3] = 8;
p[4] = 9;
p[5] = 10;
p[6] = 17;
p[7] = 17;
p[8] = 20;
p[9] = 24;
p[10] = 30;
其他情况，数组大小根据输入的n值大小动态确定，前11个值初始化为上面所提，其他为默认值0
但是该版本的运行时间随着n的增加呈指数增长，后面会给出对比曲线。
计算最优值
我们采用自底向上的动态规划的方法得到更有效的算法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public static long getCutRodDP(long[] p, int n) {
long[] dp = new long[n + 1];
int[] length = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
long q = Long.MIN_VALUE;
for (int j = 1; j <= i; j++) {
long temp = q;
q = j < p.length ? Math.max(q, p[j] + dp[i - j]) : Math.max(q, dp[j] + dp[i - j]);
if (temp < q) {
length[i] = j;
}
}
dp[i] = q;
}
return dp[n];
}
|
p表示价格表，如本文中应该为p的数组大小应该为11。
动态规划版本与递归版本时间消耗对比如下,可以明显看到递归版本的时间呈指数增长
当钢条长度增长到35时，鄙人渣渣电脑就跑不动了，以下表示动态规划算法版本的时间消耗表
| 长度 | 200 | 400 | 600 | 800 | 1000 | 1500 | 2000 | 4000 | 6000 | 10000 |
|---|---|---|---|---|---|---|---|---|---|---|
| 耗时(ms) | 1 | 3 | 4 | 6 | 7 | 11 | 13 | 29 | 54 | 133 |
构造最优解
前面我们进给出最优解的值，并没给出具体切割方案
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public static String getCutRodDP(long[] p, int n) {
long[] dp = new long[n + 1];
int[] length = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
long q = Long.MIN_VALUE;
for (int j = 1; j <= i; j++) {
long temp = q;
q = j < p.length ? Math.max(q, p[j] + dp[i - j]) : Math.max(q, dp[j] + dp[i - j]);
if (temp < q) {
length[i] = j;
}
}
dp[i] = q;
}
//构造最优解
int temp = n;
StringBuffer str = new StringBuffer("r" + n + "=" + dp[n] + "," + "切割方案" + n + "=");
while (temp > 0) {
str.append(length[temp]);
str.append("+");
temp = temp - length[temp];
}
str.delete(str.length() - 1, str.length());
return str.toString();
}
|
测试
r11=31,切割方案11=1+10，
r15=43,切割方案15=2+3+10，
r33=98,切割方案33=3+10+10+10
完整代码以及相应示例图见 https://github.com/lemon2013/algorithm/blob/master/src/com/pty/graph/Cutrod.java
- 本文作者： lemon
- 本文链接： https://lemon2013.github.io/2017/05/31/dynamic-programming/
- 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！