问题描述
Seriling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。
假定我们知道Serling公司出售一段长为
i
i
i
英寸的钢条的价格为
p
i
p_i
p
i
(
i
=
1
,
2
,
.
.
.
,
i=1, 2, … ,
i
=
1
,
2
,
.
.
.
,
单位为美元)。钢条的长度均为整英寸。下表给出一个价格表样例。
长度 i i |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
价格 p i p_i |
1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
正式的问题描述为:给定一段长度为n英寸的钢条和一个价格表
p
i
(
i
=
1
,
2
,
.
.
.
,
n
)
p_i(i=1, 2, …, n)
p
i
(
i
=
1
,
2
,
.
.
.
,
n
)
,求切割方案,使得销售的收益
r
n
r_n
r
n
最大。注意,如果长度为n英寸的钢条价格
p
n
p_n
p
n
足够大,最优解可能就是完全不需要切割。
考虑n=3的情况,我们用一组数字来表示一种可能的切割情况,共有(3),(1, 2),(2, 1),(1, 1, 1)四种可能。卖出获得的收益分别是8,6,6,3美元。
对一个长度为n的钢条,在距离左端
i
i
i
英寸处我们可以选择切或不切,所以总共有
2
n
−
1
2^{n-1}
2
n
−
1
种切割方案。假设最优的方案是切为k段(
1
≤
k
≤
n
1 \leq k \leq n
1
≤
k
≤
n
),每段长为
i
k
i_k
i
k
,那么最优切割方案可表示为
n
=
i
1
+
i
2
+
.
.
.
+
i
k
n=i_1 + i_2 + … + i_k
n
=
i
1
+
i
2
+
.
.
.
+
i
k
该方案下的最大收益为
r
n
=
p
i
1
+
p
i
2
+
.
.
.
+
p
i
k
r_n = p_{i_1} + p_{i_2} + … + p_{i_k}
r
n
=
p
i
1
+
p
i
2
+
.
.
.
+
p
i
k
对于上述价格表样例,我们先给出长度10英寸以内所有钢条的最优切割方案及其对应收益:
r
1
=
1
,
1
=
1
r_1=1, 1=1
r
1
=
1
,
1
=
1
(无切割)
r
2
=
5
,
2
=
2
r_2=5, 2=2
r
2
=
5
,
2
=
2
(无切割)
r
3
=
8
,
3
=
3
r_3=8, 3=3
r
3
=
8
,
3
=
3
(无切割)
r
4
=
10
,
4
=
2
+
2
r_4=10, 4=2+2
r
4
=
1
0
,
4
=
2
+
2
r
5
=
13
,
5
=
2
+
3
r_5=13, 5=2+3
r
5
=
1
3
,
5
=
2
+
3
r
6
=
17
,
6
=
6
r_6=17, 6=6
r
6
=
1
7
,
6
=
6
(无切割)
r
7
=
18
,
7
=
1
+
6
或
7
=
2
+
2
+
3
r_7=18, 7=1+6或7=2+2+3
r
7
=
1
8
,
7
=
1
+
6
或
7
=
2
+
2
+
3
r
8
=
22
,
8
=
2
+
6
r_8=22, 8=2+6
r
8
=
2
2
,
8
=
2
+
6
r
9
=
25
,
9
=
3
+
6
r_9=25, 9=3+6
r
9
=
2
5
,
9
=
3
+
6
r
1
0
=
30
,
10
=
10
r_10=30, 10=10
r
1
0
=
3
0
,
1
0
=
1
0
(无切割)
问题求解
下面来求解切割钢条问题。首先我们注意到,对于
r
n
(
n
≥
1
)
r_n(n\geq1)
r
n
(
n
≥
1
)
可以用更短的钢条的最优收益来描述它:
r
n
=
m
a
x
(
p
n
,
r
1
+
r
n
−
1
,
r
2
+
r
n
−
2
,
.
.
.
,
r
n
−
1
+
r
1
)
r_n=max(p_n, r_1+r_{n-1}, r_2+r_{n-2}, … , r_{n-1}+r_1)
r
n
=
m
a
x
(
p
n
,
r
1
+
r
n
−
1
,
r
2
+
r
n
−
2
,
.
.
.
,
r
n
−
1
+
r
1
)
即在只切一次后钢条被分成的两段的情况下,这两段钢条的最优收益之和的最大值,即为原钢条的最优收益。其中完全不切割的情况表示为
p
n
p_n
p
n
。
更加一般概括的说,为了求解规模为n的原问题,我们先求解形式完全一样,但规模更小的自问题。这些子问题的最优解组合起来,就构成了原问题的解。
这种性质称为
最优子结构性质(optimal substructure)
:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。
递归求解
除了上述方法外,还有一种更为简洁的递归求解法。将钢条从左端起切下长为
i
i
i
的一段,这一段将不再被切割,只对右边剩下的长度为
n
−
i
n-i
n
−
i
的一段继续进行切割。这样一来,长度为
n
n
n
的钢条的收益就被分解为长度为
i
i
i
的钢条按照价格表上的收益与长度为
n
−
i
n-i
n
−
i
的钢条继续切割得到的最优收益之和。而原钢条的最优收益就等于所有可能的
i
i
i
之中收益和最大的那个值。即
r
n
=
max
1
≤
i
≤
n
(
p
i
+
r
n
−
i
)
r_n=\mathop{\max}_{1\leq i \leq n}(p_i + r_{n-i})
r
n
=
max
1
≤
i
≤
n
(
p
i
+
r
n
−
i
)
该方法的python实现如下:
import sys
sys.setrecursionlimit(100) #增大递归次数限制
p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30] #价格表
def cut_rod(p, n):
if n == 0: #递归终止条件
return 0
q = -1
for i in range(n):
q = max(q, p[i] + cut_rod(p, n-i-1)) #递归比对所有i的收益,求最大值
return q
该方法看似简单有效,然而在递归过程中执行了很多重复运算。对于一个子问题,在求解所有规模比它大的问题的时候都会重新被计算一遍,这使其效率大大被降低。具体过程中,对
i
=
1
,
2
,
.
.
.
,
n
i=1, 2, …, n
i
=
1
,
2
,
.
.
.
,
n
调用
c
u
t
_
r
o
d
(
p
,
n
−
i
)
cut\_rod(p, n-i)
c
u
t
_
r
o
d
(
p
,
n
−
i
)
等价于对
j
=
0
,
1
,
.
.
.
,
n
−
1
j=0,1, …, n-1
j
=
0
,
1
,
.
.
.
,
n
−
1
调用
c
u
t
_
r
o
d
(
p
,
j
)
cut\_rod(p, j)
c
u
t
_
r
o
d
(
p
,
j
)
。可见在递归过程中重复调用的次数会指数增长。令
T
(
n
)
T(n)
T
(
n
)
表示第二个参数值为
n
n
n
时
c
u
t
_
r
o
d
cut\_rod
c
u
t
_
r
o
d
的调用次数。因为
c
u
t
_
r
o
d
(
p
,
n
)
cut\_rod(p, n)
c
u
t
_
r
o
d
(
p
,
n
)
本身也算作一次调用,故
T
(
0
)
=
1
T(0)=1
T
(
0
)
=
1
,且
T
(
n
)
=
1
+
∑
k
=
1
n
−
1
T
(
k
)
T(n)=1+\sum_{k=1}^{n-1}T(k)
T
(
n
)
=
1
+
k
=
1
∑
n
−
1
T
(
k
)
第一项的1表示调用
c
u
t
_
r
o
d
(
p
,
n
)
cut\_rod(p, n)
c
u
t
_
r
o
d
(
p
,
n
)
函数本身,
T
(
k
)
T(k)
T
(
k
)
为函数内部调用
c
u
t
_
r
o
d
(
p
,
n
−
i
)
cut\_rod(p, n-i)
c
u
t
_
r
o
d
(
p
,
n
−
i
)
时产生的所有调用次数(包括递归调用)。证明略,结论为
T
(
n
)
=
2
n
T(n)=2^n
T
(
n
)
=
2
n
,即对于长为
n
n
n
的钢条,调用次数为
2
n
2^n
2
n
。
使用动态规划求解
前述问题暴露的缺陷是递归过程中反复求解相同的子问题。为了避免这样的浪费,动态规划方法合理安排求解的顺序,对每个子问题只求解一次,并将结果保存下来。如果之后需要再次求解该问题,则直接使用已保存的结果。因此,动态规划是典型的用空间换时间的方法。以切割钢条问题为例,动态规划可以有两种等价的实现方法。第一种称为
带备忘的自顶向下法(top-down with memoization)
,第二种称为
自底向上法(bottom-up method)
。
带备忘的自顶向下法
此方法仍然按照正常的递归形式实现过程,但在过程中每求解一个新的子问题就会将其结果保存下来。当重复需要某个子问题的解时,则直接读取保存的值即可。
p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
memo = [ -1 for _ in range(n) ]
def cut_rod(p, n):
if n == 0:
return 0
if memo[n-1] > 0: #memo的下标从0开始,而n是自然下标需要变换
return memo[n-1]
q = -1
for i in range(n):
q = max(q, p[i] + cut_rod(p, n-i-1))
memo[n-1] = q
return q
自底向上法
此方法需要恰当定义子问题的规模,使得任何子问题的求解都只依赖于”更小的“子问题的解,然后按照从小到达的顺序求解问题。这样一来,在求解某个子问题时,它所依赖的那些更小的问题都已经求解完毕,结果已经保存。
p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
r = [ 0 for _ in range(n+1) ] #此处使用自然下标,0即为长度为0的钢条
def bottom_up_cut_rod(p, n):
for j in range(1, n+1): #规模从小到大求解所有子问题
#此处的求解方法与自顶向下相同
q = -1
for i in range(1, j+1):
q = max(q, p[i-1] + r[j-i])
r[j] = q
return r[n]