南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）动态规划

计算机问题求解一论题3-1 动态规划 2020年09月15日

计算机问题求解 – 论题3-1 - 动态规划 2020年09月15日

Rod Cutting Problem The rod-n proble is the following.Given a rod of lengthninches and a table of prices pi for i=1,2..determine the maximum revenueobtain- able by ctin up the rod and selling the pieces. 一个样本输 入及其解： length i 1234567 89 10 price Pi 1589101717 202430 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, rio 30 from solution 10=10 (no cuts). f

Rod Cutting Problem 一个样本输 入及其解： r7 :

问题1： 这个问题的解空间有多 大？为什么？

问题2 如何搜索？可以压缩解空间吗？ 似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样

似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样

间题3：如何思考？ 第一刀切下去之后： 针对任意的r,我们能够写出下面的公式！ Tn=ri+rn-i 当i从1递增到-1时，我们找到了一个遍历解空间的科学手法

rn : i rn =ri+rn-i 第一刀切下去之后： 针对任意的rn，我们能够写出下面的公式！ 当i从1递增到n-1时，我们找到了一个遍历解空间的科学手法

更关键的是：我们从公式中的ri 求解中，看到了什么？ In Tn=ri+rn-i 递归！

rn : i rn =ri+rn-i 递归！

递归的解法：扫描所有可能的割法 In max (Pn,rI In-1,r2 +In-2,...,In-1+r1) max (Pi+rn-i) <i<刀 Cut-Rod(p,n){ P:价格表，n:长度 if n==0 return 0; q=-1; for(i=1 to n){ ∥递归遍历所有的“割法” q max(q,p[i]+Cut-Rod(p,n-i)) return q;

递归的解法：扫描所有可能的割法 Cut-Rod(p,n) { //P:价格表，n:长度 if n==0 return 0; q=-1; for( i=1 to n) { //递归遍历所有的“割法” q = max(q, p[i]+Cut-Rod(p, n-i)) } return q; }

递归的解法： CUT-ROD(P.n) 1fn==0 2 return 0 3q.=-00 4 for i Iton 5 4 max(g.pli]+CUT-ROD(p,n-i)) 6 return q 3 0 问题4： 为什么这个算法注 定是低效率的？

递归的解法：

Fibonacci:F=F+Fn2 间题5： 如果要你计算第n个 Fibonacci数，你用递归还是 用循环，还是随便？为什么？

递归可能代价高昂 计算第n个Fibonacci数 其实可以在线性时间内 (以加法次数计量)完成。 1 6 5 4 18 23 4 3 12 3 13 16 9 9 2 25 10 但如果采用递归，递归 调用的次数是2Fn+1~1

递归可能代价高昂 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 4 3 3 3 6 5 4 13 16 10 11 9 8 12 3 4 5 6 7 14 15 21 2 1 19 18 17 25 23 24 22 20 计算第n个Fibonacci数 其实可以在线性时间内 (以加法次数计量)完成。 但如果采用递归，递归 调用的次数是 2Fn+1-1