当前位置：首页 > news >正文

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

news 2025/6/23 13:33:45

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

问题描述

给定长度为 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 是第一段切割的长度。

算法步骤

初始化：
- 创建数组 r[0..n] 存储最大收益，r[0] = 0。
- 创建数组 s[0..n] 存储切割方案，s[i] 记录长度为 i 时第一段切割的长度。
自底向上计算：
- 遍历长度 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。
回溯切割方案：
- 从 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**18for j in range(1, i + 1):if j > m:  # j超出价格表范围continuetemp = p[j] + r[i - j]if temp > q:q = temps[i] = jr[i] = q# 回溯切割方案solution = []i = nwhile 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]