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]]进行判断，逐步地找出具体的最佳方案了。

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