算法-动态规划-钢条切割问题

钢条切割问题是一个经典的动态规划问题，旨在通过切割钢条获得最大收益。以下是详细解释和解决方案：

问题描述

• 给定长度为 n 的钢条和价格表 p，其中 p[i] 表示长度为 i 的钢条的价格（i = 1, 2, ..., n）。
• 目标：找到切割方案，使销售收益最大化。

动态规划解法

核心思想

• 最优子结构：长度为 n 的钢条的最优解包含子问题的最优解（例如，切割成两段后，每段的最优解）。
• 递归关系：

  • 设 r[i] 为长度为 i 的钢条的最大收益。

  • 初始值：r[0] = 0（长度为 0 的钢条收益为 0）。

  • 递推公式：

    r[i] = max_{1≤j≤min(i, m)} { p[j] + r[i - j] }

    其中 m 是价格表的最大长度（即 m = len(p)），j 是第一段切割的长度。

算法步骤

1. 初始化：

   • 创建数组 r[0..n] 存储最大收益，r[0] = 0。
   • 创建数组 s[0..n] 存储切割方案，s[i] 记录长度为 i 时第一段切割的长度。

2. 自底向上计算：

   • 遍历长度 i 从 1 到 n：
     • 初始化 q = -∞（临时变量，存储当前最大收益）。
     • 遍历切割长度 j 从 1 到 i：
       • 若 j 超出价格表范围（j > m），跳过。
       • 否则，计算收益 temp = p[j] + r[i - j]。
       • 若 temp > q，更新 q = temp 并记录 s[i] = j。
     • 设置 r[i] = q。

3. 回溯切割方案：

   • 从 i = n 开始：
     • 输出 s[i]（第一段切割长度）。
     • 更新 i = i - s[i]，重复直到 i = 0。

时间复杂度和空间复杂度

• 时间复杂度：O(n^2)（双重循环）。
• 空间复杂度：O(n)（存储 r 和 s 数组）。

示例演示

假设 n = 4，价格表 p = [0, 1, 5, 8, 9]（索引从 1 开始）：

• 计算过程：
  • i=1：j=1 → r[1] = p[1] + r[0] = 1，s[1]=1
  • i=2：j=1 → 1 + r[1]=2；j=2 → 5 + r[0]=5 → r[2]=5, s[2]=2
  • i=3：j=3 → 8 + r[0]=8 → r[3]=8, s[3]=3
  • i=4：j=2 → 5 + r[2]=10 → r[4]=10, s[4]=2
• 切割方案：4 → 2 + 2（收益 5 + 5 = 10）。

**代码实现（Python）

def rod_cutting(n, p):
    m = len(p) - 1  # 价格表最大长度（索引从1开始）
    r = [-10**18] * (n + 1)  # 最大收益数组
    s = [0] * (n + 1)         # 切割方案数组
    r[0] = 0     # 初始化
    
    # 动态规划填表
    for i in range(1, n + 1):
        q = -10**18
        for j in range(1, i + 1):
            if j > m:  # j超出价格表范围
                continue
            temp = p[j] + r[i - j]
            if temp > q:
                q = temp
                s[i] = j
        r[i] = q
    
    # 回溯切割方案
    solution = []
    i = n
    while i > 0:
        solution.append(s[i])
        i -= s[i]
    
    return r[n], solution

示例

n = 4
p = [0, 1, 5, 8, 9] # p[0]无效，p[1]=1, p[2]=5, …
max_profit, cuts = rod_cutting(n, p)
print(“最大收益:”, max_profit) # 输出: 10
print(“切割方案:”, cuts) # 输出: [2, 2]

关键点

• 价格表处理：索引从 1 开始，p[j] 直接对应长度 j 的价格。
• 边界处理：当 j > m 时跳过（长度超出价格表范围）。
• 方案回溯：利用 s 数组逐步还原切割段。

此方法高效地解决了钢条切割问题，适用于任意长度的钢条和价格表。