动态规划案例分析.ppt
《动态规划案例分析.ppt》由会员分享,可在线阅读,更多相关《动态规划案例分析.ppt(32页珍藏版)》请在三一文库上搜索。
1、动态规划 案例分析 2019/2/91 数字三角形 1、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很 多条不同的路径。对于每条路径,把路径上面的数加起来可以 得到一个和,和最大的路径称为最佳路径。你的任务就是求出 最佳路径上的数字之和。 注意:路径上的每一步只能从一个数走到下一层上和它最近的 左边的数或者右边的数。 问题描述 输入数据 输入的第一行是一个整数N (1 #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int MaxSum( int r, int j) if( r = N ) return Drj;
2、 int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 ) return nSum1+Drj; return nSum2+Drj; 3、参考程序 I int main(void) int m; scanf(“%d“, for( int i = 1; i #include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int MaxSum( int r, int
3、 j) if( r = N ) return Drj; if( aMaxSumr+1j = -1 ) /如果MaxSum(r+1, j)没有计算过 aMaxSumr+1j = MaxSum(r+1, j); if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1); if( aMaxSumr+1j aMaxSumr+1j+1 ) return aMaxSumr+1j +Drj; return aMaxSumr+1j+1 + Drj; 4、参考程序 II int main(void) int m; scanf(“%d“, /将 aMaxSu
4、m 全部置成-1, 开始时所有的 MaxSum(r, j)都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( int i = 1; i 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(“%d“, aMaxSum11); return 0; 思考题:上面的几个程序 只算出了最佳路径的数字 之和。如果要求输出最佳 路径上的每个数字,该怎 么办? 动态规划解题的一般思路
5、n 许多求最优解的问题可以用动态规划来解决。 n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导 致子问题被重复计算,用动态规划的方法,子问题的解一旦求出就 要被保存,所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似,有时甚至完全一样,只不过规模 从原来的n 变成了n-1,或从原来的nm 变成了n(m-1) 等 等。 n 找到子问题,就意味着找到了将整个问题逐渐分解的办法。 n 分解下去,直到最底层规模最小的的子问题可以一目了然地看出 解。 n 每一层子问题的解决,会导致上一层子问题的解决,逐层向上, 就会导致最终整个问题的解决。 n 如果从最底层的子问题开始,自底向上地
6、推导出一个个子问题的 解,那么编程的时候就不需要写递归函数。 动态规划解题的一般思路 n 用动态规划解题时,将和子问题相关的各个变量的一组取值 ,称之为一个“状态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“值”,就是这个“状态”所对应的子问题的 解。 n 比如数字三角形,子问题就是“从位于(r,j)数字开始,到底 边路径的最大和”。这个子问题和两个变量r 和j 相关,那么一 个“状态”,就是r, j 的一组取值,即每个数字的位置就是一个“ 状态”。该“状态”所对应的“值”,就是从该位置的数字开始, 到底边的最佳路径上的数字之和。 n 定义出什么是“状态”,以及在该 “状态”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 案例 分析
链接地址:https://www.31doc.com/p-2063771.html