NOIP普及讲座3-动态规划1.ppt

《NOIP普及讲座3-动态规划1.ppt》由会员分享，可在线阅读，更多相关《NOIP普及讲座3-动态规划1.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP普及讲座3-动态规划1引例（数塔问题）引例（数塔问题）设有一个三角形的数塔，顶点为根结点，每个结设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向点有一个整数值。从顶点出发，可以向左走或向右走，从根结点右走，从根结点1313出发向左、向右的路径长度可出发向左、向右的路径长度可以是：以是：131311117 714147 7，其和为，其和为525213131111121214141313，其和为，其和为6363若要求从根结点开始，若要求从根结点开始，请找出一条路径，使请找出一条路径，使路径之和最大路径之和最大,输出路输出路 径的长度。径的长度。13151

2、41124131211876872612引引例例（数数塔塔问问题题）1315141124131211876872612动动态态规规划划的的基基本本概概念念（1）阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。（2）状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问题过程中的状况。（3）决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。动动态态规规划划的的基基本本概概念念（4）策略和最优策略：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。在实际问题中，从决策允许集合中找

3、出最优效果的策略称为最优策略。（5）状态转移方程：状态转移方程是确定两个相邻阶段状态的演变过程。运运用用动动态态规规划划的的条条件件（1）最优化 子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说问题的一个最优解中包含着子问题的一个最优解。（2）无后效性 当前阶段中的状态只能由上一个阶段中的状态转移方程得来，与其他阶段的状态没有关系，特别是与未发生的阶段状态没有关系，这就是无后效性。动动态态规规划划算算法法的的一一般般模模式式（1 1）划分阶段：按照问题的时间或空间特征，把）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段；问题分为若干个阶段；（2 2）确定

4、状态和状态变量：将问题发展到各个阶）确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同状态表示出来；段时所处的各种情况用不同状态表示出来；（3 3）确定决策并写出状态转移方程：一般是根据）确定决策并写出状态转移方程：一般是根据相邻两个阶段各状态之间的关系来确定决策；相邻两个阶段各状态之间的关系来确定决策；（4 4）寻找边界条件：给出的状态转移方程是一个）寻找边界条件：给出的状态转移方程是一个递推式，必须有一个递推的边界条件；递推式，必须有一个递推的边界条件；（5 5）编写程序。）编写程序。经经典典例例题题讲讲解解【例题例题1 1】拦截导弹（】拦截导弹（noi openjudge 8

5、780noi openjudge 8780）问题描述：问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。截所有的导弹。

6、输入导弹依次飞来的高度（雷达给出的高度数据是不大于输入导弹依次飞来的高度（雷达给出的高度数据是不大于3000030000的正整数），计算这套系统最多能拦截多少导弹。的正整数），计算这套系统最多能拦截多少导弹。经经典典例例题题讲讲解解输入输入第一行是一个整数第一行是一个整数NN（不超过（不超过1515），表示导弹数。），表示导弹数。第二行包含第二行包含NN个整数，为导弹依次飞来的高度（雷达给出的高个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于度数据是不大于3000030000的正整数）。的正整数）。输出输出一个整数，表示最多能拦截的导弹数。一个整数，表示最多能拦截的导弹数。样例输入样例

7、输入8 8389 207 155 300 299 170 158 65389 207 155 300 299 170 158 65样例输出样例输出6 6经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：fifi代表打下第代表打下第i i颗导弹最多能打多少颗导弹颗导弹最多能打多少颗导弹方程：方程：fi=max(fj)+1(1=ji)fi=max(fj)+1(1=ji)且第且第i i颗导弹的高度要高于颗导弹的高度要高于第第j j颗导弹的高度颗导弹的高度 【程序实现程序实现】经经典典例例题题讲讲解解【例题例题2 2】饥饿的牛饥饿的牛问题描述：问题描述：牛在饲料槽前排好了队。饲料槽依次用牛在饲料

8、槽前排好了队。饲料槽依次用1 1到到N(1=N=2000)N(1=N=2000)编号。每编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。约翰提供约翰提供B B个区间的清单。一个区间是一对整数个区间的清单。一个区间是一对整数start-start-end,1=start=end=Nend,1=start=end=N，表示一些连续的饲料槽，比如，表示一些连续的饲料槽，比如1-3,7-8,3-1-3,7-8,3-4 4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。

9、当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。些区间，使它能吃到最多的东西。在上面的例子中，在上面的例子中，1-31-3和和3-43-4是重叠的；聪明的牛选择是重叠的；聪明的牛选择1-31-3，7-87-8，这样可，这样可以吃到以吃到5 5个槽里的东西。个槽里的东西。经经典典例例题题讲讲解解【输入格式】【输入格式】第一行，整数第一行，整数B(1=B=1000)B(1=B=1000)第第2 2到到B+1B+1行，每行两个整数，表示一个区间，较小的端点在前面行，每行两个整数，表示一个区间，较

10、小的端点在前面【输出格式】【输出格式】仅一个整数，表示最多能吃到多少个槽里的食物。仅一个整数，表示最多能吃到多少个槽里的食物。【样例输入】【样例输入】3 31 31 37 87 83 43 4【样例输出】【样例输出】5 5 经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：fifi代表吃了第代表吃了第i i个区间最多能多少食物个区间最多能多少食物方程：方程：fi=max(fj)+ifi=max(fj)+i个区间的长度个区间的长度(1=ji)(1=ji)且第且第i i颗区间的颗区间的开始时间要大于开始时间要大于j j的区间的结束时间的区间的结束时间经经典典例例题题讲讲解解【例题例题3 3】

11、最长公共子序列（最长公共子序列（codevs1408codevs1408）问题描述：问题描述：熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。们要研究最长公共上升子序列了。小沐沐说，对于两个串小沐沐说，对于两个串A A，B B，如果它们都包含一段位置不一定连续的数，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子字，且数字是

12、严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。串，而所有的公共上升子串中最长的就是最长公共上升子串了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。只要告诉奶牛它的长度就可以了。经经典典例例题题讲讲解解【输入格式】【输入格式】第一行第一行NN，表示，表示A A，B B的长度。的长度。第二行，串第二行，串A A。第三行，串第三行，串B B。【输出格式】【输出格式】输出长度输出长度【样例输入】【样例输入】4 42 2 1 32 2

13、 1 32 1 2 32 1 2 3【样例输出】【样例输出】2 2【数据范围及提示】【数据范围及提示】1=N=3000 1=N=3000，A A，B B中的数字不超过中的数字不超过maxlongintmaxlongint经经典典例例题题讲讲解解【问题分析问题分析】状态状态状态状态 fi,jfi,jfi,jfi,j代表代表代表代表a a a a字符串到字符串到字符串到字符串到i,bi,bi,bi,b字符串到字符串到字符串到字符串到j j j j的最长公共字串的最长公共字串的最长公共字串的最长公共字串 方程：方程：方程：方程：ai=aj ai=aj ai=aj ai=aj 则则则则 fi,j=fi

14、-1,j-1+1;fi,j=fi-1,j-1+1;fi,j=fi-1,j-1+1;fi,j=fi-1,j-1+1;ai ai ai ai不等于不等于不等于不等于aj aj aj aj 则则则则fi,j=max(fi-1,j,fi,j-1)fi,j=max(fi-1,j,fi,j-1)fi,j=max(fi-1,j,fi,j-1)fi,j=max(fi-1,j,fi,j-1)【程序实现程序实现】【程序实现程序实现】经经典典例例题题讲讲解解【例题例题4 4】最低通行费用（最低通行费用（noi openjudge 7614noi openjudge 7614）问题描述：问题描述：一个商人穿过一个一个

15、商人穿过一个 N*N N*N 的正方形的网格，去参加一个非常重要的商务活的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间动。他要从网格的左上角进，右下角出。每穿越中间1 1个小方格，都要个小方格，都要花费花费1 1个单位时间。商人必须在个单位时间。商人必须在(2N-1)(2N-1)个单位时间穿越出去。而在经过个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿间内用最少费用穿越出去。请问至少需要

16、多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。输入输入第一行是一个整数，表示正方形的宽度第一行是一个整数，表示正方形的宽度N(1=N 100)N(1=N 100)；后面后面 N N 行，每行行，每行 N N 个不大于个不大于 100 100 的整数，为网格上每个小方格的费用。的整数，为网格上每个小方格的费用。输出输出至少需要的费用至少需要的费用.经经典典例例题题讲讲解解样例输入样例输入5 51 4 6 8 10 1 4 6 8 10 2 5 7 15 17 2 5 7 15 17 6 8 9

17、 18 20 6 8 9 18 20 10 11 12 19 21 10 11 12 19 21 20 23 25 29 33 20 23 25 29 33 样例输出样例输出109109提示提示样例中，最小值为样例中，最小值为109=1+2+5+7+9+12+19+21+33109=1+2+5+7+9+12+19+21+33。经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：fi,jfi,j代表到达代表到达i,ji,j位置的最低费用位置的最低费用方程：方程：fi,j=max(fi-1,j,fi,j-1)+ai,j;fi,j=max(fi-1,j,fi,j-1)+ai,j;【程序实现程序实

18、现】经经典典例例题题讲讲解解【例题例题5 5】机器分配机器分配 问题描述：问题描述：某总公司拥有高效生产设备某总公司拥有高效生产设备MM台，准备分给下属的台，准备分给下属的N N 个分公司。各分个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这配这 M M 台设备才能使国家得到的盈利最大？求出最大盈利值。台设备才能使国家得到的盈利最大？求出最大盈利值。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数设备数 M M。其中。其中M=100

19、M=100，N=100N=100。经经典典例例题题讲讲解解【输入格式】【输入格式】第一行为两个整数第一行为两个整数MM，NN。接下来是一个。接下来是一个NMNM的矩阵，其中矩阵的第的矩阵，其中矩阵的第i i行的第行的第j j列的列的数数 Aij Aij表明第表明第i i个公司分配个公司分配j j台机器的盈利。所有数据之间用一个空格分隔。台机器的盈利。所有数据之间用一个空格分隔。【输出格式】【输出格式】只有一个数据，为总公司分配这只有一个数据，为总公司分配这MM台设备所获得的最大盈利。台设备所获得的最大盈利。【样例输入】【样例输入】3 2 3 2 1 2 3 1 2 3 2 3 4 2 3 4【

20、样例输出】【样例输出】4 4经经典典例例题题讲讲解解【问题分析问题分析】状态：状态：fi,jfi,j代表前代表前i i个公司分配到个公司分配到j j台设备所能获得的最大盈利台设备所能获得的最大盈利方程方程fi,j=max(fi-1,j-k+ai,k)0=k=jfi,j=max(fi-1,j-k+ai,k)0=k=j 【程序实现程序实现】经经典典例例题题讲讲解解【例题例题6 6】复制书稿复制书稿问题描述：问题描述：有有MM本书（编号为本书（编号为1 1，2 2，MM），每本书都有一个页数），每本书都有一个页数（分别是（分别是P1P1，P2P2，PMPM）。想将每本都复制一份。将）。想将每本都复制

21、一份。将这这MM本书分给本书分给K K个抄写员（个抄写员（1=K=M=500)1=K=M=500)，每本书，每本书只能分配给一个抄写员进行复制。每个抄写员至少被分只能分配给一个抄写员进行复制。每个抄写员至少被分配到一本书，而且被分配到的书必须是连续顺序的。复配到一本书，而且被分配到的书必须是连续顺序的。复制工作是同时开始进行的，并且每个抄写员复制一页书制工作是同时开始进行的，并且每个抄写员复制一页书的速度都是一样的。所以，复制完所有书稿所需时间取的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找决于分配得到最多工作的那个抄写员的复制时间。试找一个最

22、优分配方案，使分配给每一个抄写员的页数的最一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小。（假设复制一页需要大值尽可能小。（假设复制一页需要1 1分钟）分钟）经经典典例例题题讲讲解解【输入格式】【输入格式】第一行两个整数第一行两个整数MM、K K；（；（K=M=100K=M=100）第二行第二行MM个整数，第个整数，第i i个整数表示第个整数表示第i i本书的页数。本书的页数。【输出格式】【输出格式】共共1 1行，复制完所有书最少用的时间（分钟）行，复制完所有书最少用的时间（分钟）【输入样例】【输入样例】9 39 31 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8

23、 9【输出样例】【输出样例】1717经经典典例例题题讲讲解解【问题分析问题分析】状态状态fi,jfi,j代笔前代笔前 i i个人写个人写j j本书所需要的最少时间。本书所需要的最少时间。方程：方程：fi,j=min(max(fi-1,k,sj-sk)fi,j=min(max(fi-1,k,sj-sk)i-1=k=j-1 i-1=k=j-1 【程序实现程序实现】动动态态规规划划小小结结 求得的一个最优解求得的一个最优解求得的一个最优解求得的一个最优解当前阶段的决策仅受前一阶段决策的当前阶段的决策仅受前一阶段决策的当前阶段的决策仅受前一阶段决策的当前阶段的决策仅受前一阶段决策的影响，并决定下一个阶

24、段的决策影响，并决定下一个阶段的决策影响，并决定下一个阶段的决策影响，并决定下一个阶段的决策当前当前当前当前阶段阶段阶段阶段i i i i多个规划多个规划多个规划多个规划(决策决策决策决策)当前最优决策当前最优决策当前最优决策当前最优决策当前非最优决策当前非最优决策当前非最优决策当前非最优决策i i i i向着目标阶段不断改变向着目标阶段不断改变向着目标阶段不断改变向着目标阶段不断改变(动态动态动态动态)规划方向规划方向规划方向规划方向目标目标目标目标阶段阶段阶段阶段初始初始初始初始阶段阶段阶段阶段动态规划动态规划动态规划动态规划动动态态规规划划小小结结动态规划和一般递推的不同点？动态规划和一

25、般递推的不同点？（1 1）递推的边界条件一般很明显，而动态规划）递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；的边界条件比较隐蔽，容易被忽视；（2 2）一般递推的公式比较单一，而动态规划）一般递推的公式比较单一，而动态规划的状态转移方程具有选择性；的状态转移方程具有选择性；（3 3）一般的递推往往是用来计数或是求一个）一般的递推往往是用来计数或是求一个值，而动态规划往往是用来求一个最优值。值，而动态规划往往是用来求一个最优值。动态规划和一般递推的相同点？动态规划和一般递推的相同点？无后效性和有边界条件。无后效性和有边界条件。课课后后练练习习推推荐荐同例题同例题习题习题1 1、最长上升子序列（、最长上升子序列（noi openjudge 1759noi openjudge 1759）习题习题2 2、最大子矩阵（、最大子矩阵（noi openjudge 1768noi openjudge 1768）习题习题3 3、过河、过河 此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!