动态规划forXP.ppt

作业一：数字三角形 嵌套矩形问题 问题描述：现有n个矩形，每个矩形给定长和宽。 任务： （1）求出最长的矩形嵌套序列，使得下一个矩形嵌套前一个矩形（下一个矩形比前一个矩形大）。 （2）如果有多解，矩形编号的字典序尽量小。 作业二：嵌套矩形问题 已知矩形分别为： A(1,2), B(5,8), C(5,9), D(6,9), E(6,8), F(7,9), G(7,10), H(6,10), I(5,10), J(8,11) 问题：找出字典序最小的最长矩形嵌套序列 硬币问题 问题描述： 有n种不同面值的硬币(每种无限多)。 任务： 给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。 作业三：硬币问题 问题描述： 有4种不同面值的硬币(每种无限多)。 面值分别为 V1=3, V1=5, V1=7, V1=14 任务： 给定S=100，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值，以及各自组合式。 The End 动态规划 郭 阳 东北大学数学系 2015年6月 学习目标 理解状态和状态转移方程 理解最优子结构和重叠子问题 熟练有向无环图（DAG）上动态规划的常见思路、两种状态定义方法和刷表法 掌握记忆化有哪些信誉好的足球投注网站在实现方面的注意事项 掌握记忆化有哪些信誉好的足球投注网站和递推中输出方案的方法 动态规划的重要性 动态规划是算法竞赛的宠儿 几乎所有算法竞赛或招聘中都有这种题目 数字三角形问题 问题描述 a. 第i层有i个结点； b. 每个结点赋予一个非负整数； c. 从顶层按箭头走到底层，如何走使途中数和尽量大？ 问题分析 若有n层，则完整路线共有 ? 条； 当n很大时遍历法的速度将让人无法忍受 数字三角形问题 状态 a. 给结点编号 b. 把位置(i,j)看成一个状态； c. 定义状态(i,j)的指标函数d(i,j)为从结点(i,j)出发时能得到的最大和（包括结点(i,j) 本身的值） 注意：在这个状态定义下，原问题的解是d(1,1)。 数字三角形问题 状态转移方程 d(i,j)=a(i,j)+max{d(i+1,j), d(i+1,j+1)} 其中a(i,j)是结点中的值。 原理：如果连“从(i+1,j)出发走到底部”这部分的和都不是最大，加上a(i,j)之后肯定也不是最大的。这个性质称为最优子结构，也描述为“全局最优解包含局部最优解” 数字三角形问题 递归算法： int solve(int i, int j){ return a[i][j] + (i==n?0:max(solve(i+1,j), solve(i+1,j+1)));} (1) 输入solve(1,1)即可递归出结果； (2) 正确但效率低，大量重复计算； (3) 调用关系树共有 ？ 个结点 程序Prog1 数字三角形问题 递推算法： int i, j; for(j=1; j=n; j++) d[n][j] = a[n][j]; for(i=n-1; i=1; i--) for(j=1; j=i; j++) d[i][j] = a[i][j] + max(d[i+1][j], d[i+1][j+1]); (1) 时间复杂度为 O( ): 为1+2+···+n个结点求指标； 复杂度=状态总数×每个状态的决策个数×决策时间 (2) 关键之处在于i是逆序枚举的。 程序Prog2 数字三角形问题 记忆化有哪些信誉好的足球投注网站： (1) “memset(d, -1, sizeof(d));” d全部初始化为-1，然后递归： int solve(int i, int j) { if (d[i][j] =0 ) return d[i][j]; return d[i][j] =a[i][j] + (i == n ? 0 : max(solve(i+1, j), solve(i+1, j+1))); } (2) 虽递归，但判断d[i][j]=0保证每个结点只访问一次 (3) 时间复杂度： O( ) 程序Prog3 数字三角形问题 --- 总结 遍历法：完整路线有 条，让人无法忍受； 递归法：共 个结点需要计算指标，重复计算； 递推法：共有