知识卡片
切杆递推包含不切方案
设 pᵢ 是长度 i 的整段售价,rⱼ 是长度 j 的杆经过最优切分后可得的最大收入,并令 r₀=0。若第一段取长度 i,剩余长度就是 n−i,因此递推在 i=1…n 中取 pᵢ+rₙ₋ᵢ 的最大值。i=n 正好表示整根不切;若排除它,pₙ 较高时会算错。
补充教学演示(价格取自书中价格表):长度 4 时,p₁…p₄=1,5,8,9,且 r₁…r₃=1,5,8。
| 首段长度 i | 候选收入 pᵢ+r₄₋ᵢ |
|---|---|
| 1 | 1+8=9 |
| 2 | 5+5=10 |
| 3 | 8+1=9 |
| 4(不切) | 9+0=9 |
因此 r₄=10,对应切成 2+2;表格演示的是递推如何比较候选,不是运行实测。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
the first piece has size i = n and revenue pn and that the remainder has size 0 with corresponding revenue r0 = 0.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [5000, 10000);Art_P450–P451)。
- 结论依据:14.1 节将切杆表示为首段 i 与余段 n−i,允许 i=n 且 r₀=0;由此对 i=1…n 枚举 pᵢ+rₙ₋ᵢ,包含不切方案。四单位杆的价格取自原书表 14.1,候选收入表是按递推补充的教学演算,不是实测结果。
- 原始内容:the first piece has size i = n and revenue p n and that the remainder has size 0 with corresponding revenue r 0 = 0.