Rod Cutting Problem Therodnrob is the following.Given a rod of length ninches and a table of prices p for i=1,2,...ndetermine the maximum revenue obtain- able bytn up the od and selling the pieces. 一个样本输 入及其解： length i 1 2 3 4 5( 6789 10 price Pi 15 89101717202430 r=1 from solution 1 =1 (no cuts), r6 17 from solution 6=6 (no cuts), r2 5 from solution 2 =2 (no cuts), 7 18 from solution 7 =1+6 or 7=2+2+3, r3 =8 from solution 3=3 (no cuts), rs 22 from solution 8=2+6, r4 10 from solution 4=2+2, r9 25 from solution 9=3+6, rs 13 from solution 5=2+3, 1o =30 from solution 10=10 (no cuts)
Rod Cutting Problem 一个样本输 入及其解： r7 :
问题4： 为什么可能的割法数量 是2n-1?
间题5： 解决间题从那里开始？ I: 我们总是要切第一刀的，但是 第一刀割在何2
我们总是要切第一刀的，但是 第一刀割在何？ r7 :
递归的解法：扫描所有可能的割法 In max (Pn;rI+In-1,2 In-2,...,In-1+r1) Tn=maX(Pi十Tm-i) 1i蛇刀 间题6： CUT-ROD(p,n) 左边的两个式子 1 if0 2 return 0 有什么区别？ 3 q=-0∞ 4 for i Iton 5 q max(q,p[i]+CUT-ROD(p,n-i)) 6 return q
递归的解法：扫描所有可能的割法
最优子结构： In max (Pn;rI In-1;r2 +In-2,...,In-1+r1) 问题7g 你能借助以上的式子解释一下 什么是最优子结构(Optimal Substructure)?
最优子结构：