vlambda博客
学习文章列表

动态规划切棍子问题再思考

今天详细对比一下切棍子问题和无限背包问题。目的是让大家看到,两个看起来不一样的问题,其本质却是完全一样的。同时,也会给出动态规划的解法。

问题回顾

给定一根长度为n的棍子,我们要将其切割出售,以便获得最大收益。从1到n的不同长度的棍子的价格是已知的。

举例如下:

长度:[1、2、3、4、5]

价格:[2、6、7、10、13 ]

棍长:5

让我们尝试切割棍子:

五件长度1 => 10

两件长度2和一件长度1 => 14

一件长度3和两件长度1 => 11

一件长度3和一件长度2 => 13

一件长度4和一件长度1 => 12

一件长度5 => 13

这表明我们通过将棍子切成两个长度为2和一个长度为1的棍子出售,可以获得最高的价格14。

和无限背包问题的对比分析

在无限背包问题中,我们有一个承重量有限的背包,这个就和切棍子问题中我们有长度有限的棍子相对应。

在无限背包中,我们有固定种类但是不限数量的物品可供选择,在切棍子问题中,我们有长度种类有限但不限切割次数的棍子段可供选择。

在无限背包问题中,我们的目的是在满足承重量约束的前提下,使用给我们的选择,获得最大的价值。在切棍子问题中,我们的目的是在满足棍子总长度约束的前提下,使用给我们的选择,获得最大的价值。

通过这三点分析,我们不难发现,它们就是「完全一样」的问题!

进一步将,他们都是「在一定的约束条件下,寻找最优解」的问题。

到这里,你是否有某种感悟呢?

没错,这其实给我们一个很大的启发。就是凡是约束优化问题,都可以直接尝试动态规划。动态规划一般需要填一个二维数组,这个二维数组的两个维度,实际上就对应了「两个约束条件」。

以上的思考,可以有效地帮助我们决定两件事,所面对的问题是否可以尝试动态规划,如何确定二维数组的两个维度?

自底向上加表格

自上而下加记忆的方案,目标就是解决当前的问题。

自底向上加表格的思路则更彻底,目的是解决各种可能的约束条件下的问题,当前问题的解只是其中一项而已。

实现代码和无限背包问题是完全一样的。如下所示:

def solve_rod_cutting(lengths, prices, n):
lengthCount = len(lengths)
# 正确性和边界条件检查
if n <= 0 or lengthCount == 0 or len(prices) != lengthCount:
return 0

dp = [[0 for _ in range(n+1)] for _ in range(lengthCount)]

# 填充表格
for i in range(lengthCount):
for length in range(1, n+1):
p1, p2 = 0, 0
if lengths[i] <= length:
p1 = prices[i] + dp[i][length - lengths[i]]
if i > 0:
p2 = dp[i - 1][length]
dp[i][length] = max(p1, p2)

# 数组右下角的值就是我们的答案
return dp[lengthCount - 1][n]

找出最佳方案

为了找出具体的最佳切割方案,我们还是要观察上面的递推式。

我们已经知道最大的价值就是数组的右下角的值。那么这个值是如何来的呢?

从dp[i][length] = max(p1, p2)可以看到,这个价值,只可能从两种情况得来,一种是包含了最后一个棍子段,一个是没有包含最后一个棍子段。

我们只需要将这个值和它在二维数组正上面的值进行比较,如果相等,表示它是不包含最后一个棍子段得来的,即代码中的p2,如果不相等,表示它是包含了最后一个棍子段再加上dp[i][length - lengths[i]]的最优解得来的。

然后我们就可以用上面的方法继续对dp[i][length - lengths[i]]进行判断,逐步地找出具体的最佳方案了。

总结一下,实际上,上面的过程就是我们做选择的逆过程,只要你始终「聚焦到当前最优解是从哪里来的」,就可以逐步解出答案。


往期精彩回顾