CSCI3160 L07 钢条切割与最优方案恢复

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L07 钢条切割与最优方案恢复 · 原件 L07-DP-02-Rod-Cutting-未核-隐藏.pdf（本地课件） p.1–8 定位：把价格问题化成 L06 的递推，并在算最优值的同时记录选择，恢复实际切法。 承接：#L06-03 二次时间的填表算法

p.1 标题页。

输入价格不等于最优收入（p.2–3）【新】

题面（L07-DP-02-Rod-Cutting-未核-隐藏.pdf · Rod Cutting · p.2）

p.2 Input: a rod of length n an array P of length n where P[i] is the price for a rod of length i, for each $i\in[1,n]$ Goal: Cut the rod into segments of integer lengths to maximize the revenue.

表（题面，p.3）：长度与整段售价。

图（p.3）：长度 4 的全部八种有序切法。 元素：(a)4，(b)1+3，(c)2+2，(d)3+1，(e)1+1+2，(f)1+2+1，(g)2+1+1，(h)1+1+1+1。 看什么：图上标的是每段售价；整根卖 9 不一定最好。

算一遍：八种收入依次为 9、1+8=9、5+5=10、8+1=9、1+1+5=7、1+5+1=7、5+1+1=7、1+1+1+1=4。最大 10，对应两段长度 2。P[4]=9 是输入价格，opt(4)=10 是允许切割后的最优收入。

枚举第一段，剩下必须最优（p.4–5）【延伸 L06 p.3】

p.4 The key to solving the problem is to identify its underlying recursive structure.

p.4 提醒先定义子问题，不要先画一个表再猜填什么。定义 opt(k) 为长度 k 的钢条允许切割后的最大收入；空钢条 opt(0)=0。

p.5 Conditioned on the first segment having length i, the highest revenue attainable is P[i] + opt(n − i).

p.5 固定第一段长度 i 后，它贡献 P[i]；剩下 n−i 的切法若不是最优，就能换成更好切法并增加总收入。因此最优方案必在这些候选中，反之任意候选都是合法切法，得到

原页在“第一段长度范围”一句写了 $[1,x]$，但该页未定义 x；结合同页求和上界 n，实际枚举的是 1 到当前总长度。这里使用 k 表示当前子问题长度，避免把整题长度和当前状态混在一起。

这正是 #L06-03 的递推。用 p.3 价格，opt(1)=1、opt(2)=max(2,5)=5、opt(3)=max(6,6,8)=8、opt(4)=max(9,10,9,9)=10。枚举包含 i=k，即“不切”，所以不会漏掉直接出售的可能。

按长度递增计算的完整值表过程可以直接在本篇使用：先置 opt[0]=0；依次处理 k=1,…,n，每轮枚举 i=1,…,k 并取最大。候选使用的 k−i 都小于 k，故查询时已经算好。候选总数为 $\sum_{k=1}^n k=n(n+1)/2$，单个候选只有一次相加和比较，时间 $O(n^2)$，值数组空间 $O(n)$。无需另打开上一讲才能实现本题。

只知道 10，还不知道怎么切（p.6–7）【新】

p.6 This can be done by recording which subproblem yields opt(n).

p.6 指出算法还需输出实现最优值的方案。每次发现更好的候选，不仅更新 opt(k)，还存下当时选的 i。讲义把这项记为 bestSub(k)，但它实际保存的是第一段长度，不是剩余长度 k−i。

表（p.7）：最优值与对应选择。

从长度 4 出发，读 bestSub(4)=2，输出一段 2，剩余 2；再读 bestSub(2)=2，输出一段 2，剩余 0，停止。收入 5+5=10，段长和 2+2=4，两项都核验。若并列最优，可任选一个 i，仍能恢复某个最优方案。

补充：把值表与选择表成对更新。 填 k=4 时，候选及记录的变化如下，沿用原价格并约定只有严格改善才更新：

值改善时若忘记同步记录 i，可能打印出收入 10 却恢复出收入 9 的切法。回溯不能一直读 bestSub[n]，而要读当前剩余长度的选择；每次扣掉一段后，子问题已经换了。验证输出时同时检查段长全为正、总长等于输入长度、售价之和等于 opt(n)。

Piggyback 为何不增加渐近成本（p.8）

p.8 The method of using the bestSub function to generate an optimal cutting is known as the piggyback technique.

Piggyback 是在已有计算中“顺带记录决策”：每次 max 比较本来就要做，多存一个整数只增加常数工作。填表仍为 $O(n^2)$，增加一个长度 n 的选择数组。

回溯时每输出一段，剩余长度至少减少 1，所以最多 n 步，耗时 $O(n)$。它不会重新递归尝试全部切法，而是只沿已经选好的最优分支走一次。

当 P[i]+opt[k-i] 改善 opt[k] 时：
  opt[k] = P[i]+opt[k-i]
  bestSub[k] = i
恢复时令 remaining = n
while remaining > 0：
  i = bestSub[remaining]
  输出长度 i
  remaining = remaining-i

考试角度：（C 级 通识）常见考法是同时填最优值表与选择表，再写出恢复的切法；缺题干的 Midterm-A-2025T1 Q3 只列出值，不能据此补造它的原价格表。

补充对应的往年题演练见附录 A1。

本讲核心考点

• 先定义opt为切割后的最优收入，区别输入价格（p.2–5，C 级）。
• 枚举第一段，剩余部分取最优（p.5，C 级）。
• bestSub存第一段长度，回溯减去它（p.6–8，C 级）。

附录

本讲所需过程已在正文展开。

A1 作业/往年题演练（非讲义内容）：切成单位段的最小成本

题面（Final-2024T1-缺判断-题目.pdf · Problem 7 · p.5；扫描件，视觉读取）

p.5 “Problem 7 (10 marks). Suppose that we want to cut a steel rod of n meters into n equally-long segments (i.e., each segment is 1 meter long). We resort to the Fast-Cut company that offers to cut anywhere on a rod but charges a price that depends on the rod's length $\ell$. For each $\ell\in[2,n]$, the price of Fast-Cut for cutting a rod of $\ell$ meters is $A[\ell]$, and the values of A[2], A[3], ..., A[n] are given to you in an array.”

“For example, suppose n = 4, and A[2] = 2, A[3] = 4, and A[4] = 8. You may first pay a cost of 8 to cut the rod into two 2-meter segments, and then pay a cost of 2 to cut each segment in half. In total, you pay a cost of 8 + 2 × 2 = 12.”

“Design a dynamic programming algorithm to compute the cheapest cost to cut the rod into n segments, each 1 meter long, in $O(n^2)$ time. You must (i) give the recursive function underlying your algorithm, (ii) describe the algorithm, and (iii) analyze the running time of your algorithm.”

公式按原题重排。定义 C(ℓ) 为把长度ℓ整根切成单位段的最小总费用。单位段不切，C(1)=0。ℓ≥2 时第一次切收费 A[ℓ]，位置 i 把问题分成 i 与ℓ−i 两个子问题；两段都必须继续切，因此

原题最终段长都为1，任何合法分割边界都是整数；非整数切口不会消失，所以无需枚举实数位置。按ℓ从2到n填表，依赖都更短；每格枚举ℓ−1个位置，共n(n−1)/2次，时间O(n²)、空间O(n)。原例 C(2)=2，C(3)=4+min(0+2,2+0)=6，C(4)=8+min(0+6,2+2,6+0)=12。记录 i=2，先切2+2，再分别一分为二，确实花12。这里最小化的是每次切割收费，不能直接套主讲“卖出段价相加取最大”的式子。

回到正文：本讲正文

来源与证据

• 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

• 原件：L07-DP-02-Rod-Cutting-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

• 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

• 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

• 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

• 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。