知识卡片

普通读书笔记卡 · 3623.b.1

切杆递推包含不切方案

理解等级:中级

设 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;表格演示的是递推如何比较候选,不是运行实测。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.