钢条切割

Views: --

长度为 nn 的钢条可切成若干整数长度。已知长度 ii 的售价 pip_i，求总售价最大值。它是动态规划的经典入门题：选择容易描述，重复计算也很明显。

1. 最优子结构

观察最左边第一段的长度 ii。切下它获得 pip_i，剩余长度 n−in-i 应采用最优切法。因此

rn=max⁡1≤i≤n{pi+rn−i},r0=0.r_n=\max_{1\le i\le n}\{p_i+r_{n-i}\},\qquad r_0=0.

把 i=ni=n 也包括在内，表示完全不切。

2. 为什么朴素递归很慢

递归会对每个第一刀位置继续枚举，且同一剩余长度被反复求解。可能的切法数量随 nn 指数增长，朴素实现因此是指数级。

例如求 r10r_{10} 时，r7r_7 会从“先切 3”以及许多别的递归分支再次出现。

3. 自顶向下：记忆化

solve(n):
    if value[n] is known: return value[n]
    best = -infinity
    for first = 1..n:
        best = max(best, price[first] + solve(n - first))
    value[n] = best
    return best

每个长度只真正计算一次，总时间 O(n2)O(n^2)、空间 O(n)O(n)，另有递归栈。

4. 自底向上

按长度从小到大计算：

value[0] = 0
for length = 1..n:
    value[length] = -infinity
    for first = 1..length:
        value[length] = max(
            value[length],
            price[first] + value[length - first]
        )

当计算 value[length] 时，所有更短长度已知。复杂度同样是 O(n2)O(n^2) 时间、O(n)O(n) 空间。

5. 恢复切割方案

只保存最大收入无法知道怎样切。每次更新最优值时，再记录最佳第一段长度：

s[j]=arg⁡max⁡1≤i≤j{pi+rj−i}.s[j]=\arg\max_{1\le i\le j}\{p_i+r_{j-i}\}.

从 nn 开始不断输出 s[n]s[n]，再令 n←n−s[n]n\leftarrow n-s[n]，直到长度为 0。

6. 切割成本

若每切一刀支付成本 cc，不能对“不切”也扣费。转移可写成：

rn=max⁡{pn, max⁡1≤i<n(pi+rn−i−c)}.r_n=\max\left\{p_n,\ \max_{1\le i<n}(p_i+r_{n-i}-c)\right\}.

成本足够大时，最优方案可能是不切。这也说明建立模型时，成本到底按“段数”还是按“刀数”计费必须说清。

7. 与完全背包的关系

把每种长度看成可无限使用的物品，重量为长度、价值为售价，钢条切割就是容量恰好为 nn 的完全背包。两者状态等价，但钢条切割的递推常按“第一段”讲解，完全背包更强调物品维度和枚举顺序。

8. 做题检查

  • 是否允许不切？通常允许，所以要包含 pnp_n；
  • 是否必须用完全部长度？经典问题必须，若允许废料则要改变语义；
  • 价格是否可能为负？若允许不出售，应把空方案纳入；
  • 只问最大价值，还是还要方案、方案数或最少段数？后者需要额外记录。

评论