1、大家好大家好南京信息工程大学计算机与软件学院26/11/2023闫雷鸣南京信息工程大学计算机与软件学院36/11/2023学习要点学习要点:理解动态规划算法的概念。理解动态规划算法的概念。理解动态规划算法的基本要素理解动态规划算法的基本要素（1 1）最优子结构性质）最优子结构性质（2 2）重叠子问题性质）重叠子问题性质了解设计动态规划算法的步骤。了解设计动态规划算法的步骤。(1)(1)找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。(2)(2)递归地定义最优值。递归地定义最优值。(3)(3)以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。(4)(4)根据计算
2、最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。南京信息工程大学计算机与软件学院46/11/2023分治法基本思想n简言之，将一个难以直接解决的大问题，分割将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。南京信息工程大学计算机与软件学院56/11/2023n动态规划算法
3、与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=南京信息工程大学计算机与软件学院66/11/2023n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)南京信息工程大学计算机与软件学院76/11/2023n如果能够保存已解决的
4、子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)南京信息工程大学计算机与软件学院86/11/2023n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。南京信息工程大学计算机与软件学院96/11/2023例 矩阵连乘积n给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可乘的，是可乘的，i
5、=1，2，n-1。如何确定。如何确定计算矩阵连乘积的计算次序，使得依此次计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。序计算矩阵连乘积需要的数乘次数最少。南京信息工程大学计算机与软件学院106/11/2023例 矩阵连乘积n假定假定A A为为1001001 1矩阵矩阵,B B为为1 1100100矩阵，矩阵，C C为为1001001 1矩阵矩阵,(,(A A*B B)*C C需乘法数为需乘法数为 1001001 11001001001001001001 12000020000n而而 A A*(B B*C C)所需乘法数为所需乘法数为1 11001001 1100100
6、1 11 1200200n长度长度q q的矩阵乘法链有指数量级的矩阵乘法链有指数量级(2(2n n)的可能的相的可能的相乘方式乘方式(有有q q个叶节点的二叉数的数目个叶节点的二叉数的数目).).n要找一种相乘方式要找一种相乘方式,使得元素乘法数最少使得元素乘法数最少南京信息工程大学计算机与软件学院116/11/20231050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：（1 1）单个矩阵是完全加括号的；）单个矩阵是
7、完全加括号的；（2 2）矩阵连乘积）矩阵连乘积A A是完全加括号的，则是完全加括号的，则A A可表示为可表示为2 2个个完全加括号的矩阵连乘积完全加括号的矩阵连乘积A A和和B B的乘积并加括号，即的乘积并加括号，即A=(BC)A=(BC)设有四个矩阵设有四个矩阵A,B,C,DA,B,C,D，它们的维数分别是：，它们的维数分别是：u总共有五种完全加括号的方式总共有五种完全加括号的方式南京信息工程大学计算机与软件学院126/11/2023n给定给定n n个矩阵个矩阵 ，其中其中 与与 是是可乘的。考察这可乘的。考察这n n个矩阵的连乘积个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘
8、由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复说该连乘积已完全加括号，则可以依此次序反复调用调用2 2个矩阵相乘的标准算法计算出矩阵连乘积个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iAnAAA.21南京信息工程大学计算机与软件学院136/11/2023给定给定n n个矩阵个矩阵A A1 1,A,A2 2,A,An n，其中，其中
9、AiAi与与Ai+1Ai+1是可乘的，是可乘的，i=1i=1，22，n-1n-1。如何确定计算矩阵连乘积的计算次序，使得依此次。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。计算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括
10、号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk南京信息工程大学计算机与软件学院146/11/2023u动态规划动态规划 将矩阵连乘积将矩阵连乘积A Ai iA Ai i+1+1AAj j ，简记为，简记为Ai:j Ai:j，这里，这里ij ij 考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵AkAk和和Ak+1Ak+1之间将矩阵链断开，之间将矩阵链断开，ikjikj，则其相应完全，则其相应完全加括号方式为加括号方式为).)(.(211jkkk
11、iiAAAAAA 计算量：计算量：Ai:kAi:k的计算量加上的计算量加上Ak+1:jAk+1:j的计算量，再的计算量，再加上加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的计算量相乘的计算量南京信息工程大学计算机与软件学院156/11/2023n特征：计算特征：计算Ai:jAi:j的最优次序所包含的计算矩的最优次序所包含的计算矩阵子链阵子链 Ai:kAi:k和和Ak+1:jAk+1:j的次序也是最优的。的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。题的最优解。这种性质称为最优子结构性质。问题的
12、最优子结构性质是该问题可用动态规划问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。算法求解的显著特征。南京信息工程大学计算机与软件学院166/11/2023n设计算设计算Ai:j，1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,j，则原问题的最优值为则原问题的最优值为m1,n n当当i=j时，时，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,nn当当ij时，时，jkipppjkmkimjim1,1,这里 的维数为 iAiipp1jipppjkmkimjijimjki,1,min0,1jki 的位置只有的位置只有 种种可能可能kij n 可以递归地定义可以递归地定义
13、mi,j为：为：南京信息工程大学计算机与软件学院176/11/2023n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有)(22nnnn由此可见，在递归计算时，许多子问题被重复计算多次。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面
14、需要时只要简单查案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的一下，从而避免大量的重复计算，最终得到多项式时间的算法算法南京信息工程大学计算机与软件学院186/11/2023void MatrixChain(int*p，int n，int*m，int*s)for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi
15、-1*pk*pj;if(t 0)return mij;if(i=j)return 0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;南京信息工程大学计算机与软件学院246/11/2023 给定给定n n种物品和一背包。物品种物品和一背包。物品i i的重量是的重量是w wi i，其价值为，其价值为v vi i，背，背
16、包的容量为包的容量为C C。问应如何选择装入背包的物品，使得装入背包。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大中物品的总价值最大?0-10-1背包问题是一个特殊的整数规划问题。背包问题是一个特殊的整数规划问题。niiixv1maxnixCxwiniii1,1,01南京信息工程大学计算机与软件学院256/11/2023 在在0/10/1背包问题中，需对容量为背包问题中，需对容量为c c 的背包进行装载。的背包进行装载。从从n n 个物品中选取装入背包的物品，每件物品个物品中选取装入背包的物品，每件物品i i 的重量的重量为为wi wi，价值为，价值为pi pi。对于可行的背包装
17、载，背包中物品。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即物品价值最高，即p1p1*x1+p2x1+p2*x1+.+pix1+.+pi*xi(xi(其其1=i=n1=i=n，x x取取0 0或或1 1南京信息工程大学计算机与软件学院266/11/2023设所给设所给0-1背包问题的子问题背包问题的子问题nikkkxvmaxnkixjxwknikkk,1,0的最优值为的最优值为m(i，j)，即，即m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最
18、优值。由背包问题的最优值。由0-1背包问题的最优子背包问题的最优子结构性质，可以建立计算结构性质，可以建立计算m(i，j)的递归式如下。的递归式如下。iiiiwjwjjimvwjimjimjim0),1(),1(),1(max),(nnnwjwjvjnm00),(南京信息工程大学计算机与软件学院276/11/2023int knapSack(int n,int c,int w,int v,int m6N,int x)int jmax=min(wn-1,c);for(int j=0;i=jmax;j+)mnj=0;for(int j=wn;j1;i-)jmax=min(wi-1,c);for(j
19、=0;j=jmax;j+)mij=mi+1j;for(j=wi0;j=w1)m1c=max(m1c,m2c-w1+v1);南京信息工程大学计算机与软件学院286/11/2023/traceback返回最优值返回最优值 for(int i=1;i2n时，时，算法需要算法需要(n2n)计算时间。计算时间。南京信息工程大学计算机与软件学院306/11/2023小小 结结动态规划法的定义：动态规划法的定义：在求解问题中，对于每一步决策，列出各种在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一那些肯定
20、不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证步都经过筛选，以每一步都是最优解来保证全局是最优解，这种求解方法称为动态规划全局是最优解，这种求解方法称为动态规划法。法。南京信息工程大学计算机与软件学院316/11/2023适合于用动态规划法求解的问题具有以下特点：适合于用动态规划法求解的问题具有以下特点：1、可以划分成若干个阶段，问题的求解过程就是对若干、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过程。个阶段的一系列决策过程。2、每个阶段有若干个可能状态、每个阶段有若干个可能状态3、一个决策将你从一个阶段的一种状态带到下一个阶段、一个决策将你从一个阶
21、段的一种状态带到下一个阶段的某种状态。的某种状态。4、在任一个阶段，最佳的决策序列和该阶段以前的决策、在任一个阶段，最佳的决策序列和该阶段以前的决策无关。无关。5、各阶段状态之间的转换有明确定义的费用，而且在选、各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系（即动态转移方程）。择最佳决策时有递推关系（即动态转移方程）。南京信息工程大学计算机与软件学院326/11/2023动态规划设计都有着一定的模式，一般要经历以下几个步动态规划设计都有着一定的模式，一般要经历以下几个步骤：骤：1、划分阶段：按照问题的时间或空间特征，把问题分为若、划分阶段：按照问题的时间或空间特征，把问题
22、分为若干个阶段。干个阶段。2、确定状态：将问题发展到各个阶段时所处的各种客观情、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。况用不同的状态表示出来。3、确定决策并写出状态转移方程：因为决策和状态转移有、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。移方程也就可以写出。南京信息工程大学计算机与软件学院336/11/20234、寻找边界条件：给出的状态转移方程
23、是一个递推式，需、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。要一个递推的终止条件或边界条件。5、程序设计实现：动态规划的主要难点在于理论上的设计，、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。一旦设计完成，实现部分就会非常简单。南京信息工程大学计算机与软件学院346/11/2023【例题】数字三角形问题。【例题】数字三角形问题。7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 一个数字三角形宝塔。数字三角形中的数字为不超过一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底
24、层，每一步可沿的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数左斜线向下或右斜线向下走。假设三角形行数100，编，编程求解从最顶层走到最底层的一条路径，使得沿着该路程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数由文件输入数据，文件第一行是三角形的行数N。以后。以后的的N行分别是从最顶层到最底层的每一层中的数字。行分别是从最顶层到最底层的每一层中的数字。南京信息工程大学计算机与软件学院356/11/2023如输入：57 3
25、 8 8 1 0 2 7 7 4 4 5 2 6 5 输出：30南京信息工程大学计算机与软件学院366/11/2023【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：程序如下：int amaxnmaxn,max,n,i,j;void try(x,y,dep:integer;sum:longin
26、t);if(dep=n)then if summax then max=sum;exit try(x+1,y,dep+1,sum+ax+1y);try(x+1,y+1,dep+1,sum+ax+1y+1);main()for i:=1 to n do for j:=1 to i do 从文件中读数据到ai,j;max:=0;try(1,1,1,a1,1);printf(max);但是当行数很大时，当三角形的行数等于但是当行数很大时，当三角形的行数等于100时，其枚举时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须
27、用动态规划法来解。到计算结果，必须用动态规划法来解。南京信息工程大学计算机与软件学院376/11/2023 用动态规划法解题用动态规划法解题:逆推法逆推法 按三角形的行划分阶段，若行数为按三角形的行划分阶段，若行数为 n，则可把问题看，则可把问题看做一个做一个n-1个阶段的决策问题。先求出第个阶段的决策问题。先求出第n-1阶段阶段(第第n-1行行上各点上各点)到第到第n行的最大和，再依次求出第行的最大和，再依次求出第n-2阶段、第阶段、第n-3阶段阶段第第1阶段阶段(起始点起始点)各决策点至第各决策点至第n行的最佳路径。行的最佳路径。设：设：fi,j为从第为从第i阶段中的点阶段中的点j至第至第
28、n行的最大的数字和行的最大的数字和；则则:fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=j=i，f1,1即为所求。即为所求。南京信息工程大学计算机与软件学院386/11/2023#define maxn=100;char*fname;file inputf;int n,i,j;int amaxn+1maxn+1,fmaxn+1maxn+1;.for(i=1;i=n;i+)for(j=1;j=n;j+)输入输入aij;for(i=1;i=1;i-)for(j=1;jfi+1j+1)fij=aij+fi+1j else fij=aij+fi
29、+1j+1;输出输出f11);南京信息工程大学计算机与软件学院396/11/2023顺推法顺推法 按三角形的行划分阶段，若行数为按三角形的行划分阶段，若行数为 n，则可把问题，则可把问题看做一个看做一个n-1个阶段的决策问题。先求第个阶段的决策问题。先求第2行各元素到行各元素到起点的最大和起点的最大和,再依次求出第再依次求出第3,4，5,.,.n-1,n到起点到起点的最大和的最大和,最后找第最后找第n行的最大值行的最大值设设fij为为 第第i行第行第j列上点到起点的最大和列上点到起点的最大和则则 f11=a11;fi1=ai1+fi-11;f ij=max aij+fi-1j-1,aij+fi
30、-1j 2=j=imax(fn1,fn2,.,fnn即为所求。即为所求。南京信息工程大学计算机与软件学院406/11/2023 int n,i,j,amaxnmaxn,f maxnmaxn,maxsum;main .f11=a11;for(i=2;i=n;i+)fi1=ai1+fi-11;for(j=2;jfi-1j)fij=aij+fi-1j-1 else fij=aij+fi-1j;maxsum:=0;for(i=2;imaxsum then maxsum:=fni;输出输出;南京信息工程大学计算机与软件学院416/11/2023n挖地雷挖地雷()问题描述问题描述在一条公路上埋有若干堆地雷
31、，每堆地雷有一定的在一条公路上埋有若干堆地雷，每堆地雷有一定的数量，地雷堆的编号为数量，地雷堆的编号为1，2，N，例如，埋有，例如，埋有地雷数量如下：地雷数量如下：8 14 2 17 33 26 15 17 19 6此时，地雷的数量可用一维数组此时，地雷的数量可用一维数组A（N）表示。同时，）表示。同时，给出地雷堆之间的联系，从第给出地雷堆之间的联系，从第1堆开始，它指出挖堆开始，它指出挖了此堆之后，还可以选择继续往下挖，若存在多种了此堆之后，还可以选择继续往下挖，若存在多种方案，只能选择其中的一种，若没有任何后继的方方案，只能选择其中的一种，若没有任何后继的方案，则挖地雷结束。例如，可给出下
32、面的关系案，则挖地雷结束。例如，可给出下面的关系:南京信息工程大学计算机与软件学院426/11/202313246758910 8 14 2 17 33 26 15 17 19 6 若从第若从第1堆开始挖，首先得到堆开始挖，首先得到8枚地雷，然后，下面有枚地雷，然后，下面有2种选种选择择3、4，若选择，若选择3，则可挖到，则可挖到2枚，下面还可以继续挖，或选择枚，下面还可以继续挖，或选择4此时可挖到此时可挖到17枚，到此结束，总共可挖到枚，到此结束，总共可挖到8+17=25枚。枚。或选择或选择1-3-6-7-8-10此时可挖到此时可挖到74枚。但也可以从枚。但也可以从2开开始挖，后选择始挖，后
33、选择2-3-6-7-8-10，则共可挖到，则共可挖到14+26+15+17+6=80枚，但还不是最多的，最多的为枚，但还不是最多的，最多的为5-6-7-8-10，此时共可挖到，此时共可挖到33+26+15+17+6=97枚。枚。南京信息工程大学计算机与软件学院436/11/2023 地雷堆之间的联系可用以下的数组表示地雷堆之间的联系可用以下的数组表示:二维整数型数组二维整数型数组R(i,j)R(i,j)表示，当表示，当R(i,j)=1R(i,j)=1表示从表示从i i到到j j有有通路，当通路，当R(i,j)=0R(i,j)=0表示无通路。表示无通路。南京信息工程大学计算机与软件学院446/1
34、1/2023算法分析算法分析用动态规划求解用动态规划求解:1 由后往前查找由后往前查找:若从第若从第n堆地雷开始挖，此时可能得到堆地雷开始挖，此时可能得到a(n)枚地雷。枚地雷。若从第若从第n-1堆地雷开始挖，此时有堆地雷开始挖，此时有2种可能种可能:n-1堆到堆到n堆无联系堆无联系(可由可由R(n-1，n)判断判断)，此时可挖，此时可挖a(n-1)枚。枚。n-1堆到堆到n堆有联系，则可挖堆有联系，则可挖a(n-1)+a(n)枚。枚。一般情况，若从第一般情况，若从第i堆开始挖，根据关系堆开始挖，根据关系R，找出，找出i后面后面的所有联系，从中找出一个可挖最多地雷的作为联系，这的所有联系，从中找
35、出一个可挖最多地雷的作为联系，这样可得到最多的挖地雷数。样可得到最多的挖地雷数。2 上面计算出从每个堆开始能挖到最多的地雷数，此时找上面计算出从每个堆开始能挖到最多的地雷数，此时找出一个最大值即可。出一个最大值即可。南京信息工程大学计算机与软件学院456/11/20233 算法流程。算法流程。定义数据结构，整数型二维数组定义数据结构，整数型二维数组B(N，2)B(i，1)表示最多可挖地雷数。表示最多可挖地雷数。B(i，2)向后连接。向后连接。求从第求从第i堆地雷开始挖的数量的算法堆地雷开始挖的数量的算法:for(i=N;i=1;i-)CMAX=0,H=0;for(j=i+1;jCMAX)H=j
36、;CMAX=B(j,1)B(i,1)=A(i)+CMAX B(i,2)=H南京信息工程大学计算机与软件学院466/11/2023找出最大值并找出挖的路径找出最大值并找出挖的路径:CMAX=0;H=0;for(i=1;iCMAX)THEN H=i;CMAX=Bi1;printf(最大可挖数量最大可挖数量%d：,CMAX);printf(H);while(H0)H=B(H,2);printf(h);南京信息工程大学计算机与软件学院476/11/2023动态规划动态规划-石子归并石子归并 题目描述题目描述在一个圆形操场的四周摆放着N堆石子(N=100),现要将石子有次序地合并成一堆。规定每次只能选取
37、相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。堆数N及每堆的石子数(=20).(1)选择一种合并石子的方案,做N1次合并,得分的总和最小;(2)选择一种合并石子的方案,做N1次合并,得分的总和最大;南京信息工程大学计算机与软件学院486/11/2023n输入数据输入数据:第一行为石子堆数第一行为石子堆数N;N;第二行为每堆的石子数第二行为每堆的石子数,每两个数之间用一个空格分隔。每两个数之间用一个空格分隔。n输出数据输出数据:从第一至第从第一至第N N行为得分最小的合并方案行为得分最小的合并方案.第第N+1N+1行是空行是空行。从第行。从第N+2N+2行到第行到第2N+1
38、2N+1行是得分最大合并方案行是得分最大合并方案.每种合每种合并方案用并方案用N N行表示行表示,其中第其中第i i行行(1=i=N)(1=i=N)表示第表示第i i次合并前次合并前各堆的石子数各堆的石子数(依顺时针次序输出依顺时针次序输出,哪一堆先输出均可哪一堆先输出均可).).要求将待合并的两堆石子数以相应的负数表示要求将待合并的两堆石子数以相应的负数表示.南京信息工程大学计算机与软件学院496/11/2023n输入输出范例输入输出范例:输入:44 5 9 4 输出:-4 5 9 -4-8 -5 9-13-9224 -5 -9 44 -14 -4-4-1822 石子堆数N 每堆的石子数 输
39、出数据输出数据：从第一至第N行为得分最小的合并方案。第N+1行是空行。从第N+2行到第2N+1行是得分最大合并方案。每种合并方案用N行表示,其中第i行(1=in then t(i+k)mod n else ti+k 最后一个连第一个的情况处理最后一个连第一个的情况处理 si,j最优最优si,k+st,j-k+sum1,3 sumi,j表示从表示从i开始数开始数j个数的和个数的和 end;南京信息工程大学计算机与软件学院576/11/2023小结小结 一、动态规划的实质是分治思想和解决冗余，因此它一、动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为与分治
40、法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。更小的、相似的子问题，但是动态规划又有自己的特点。贪心法的当前选择可能要依赖于已经作出的选择，但贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。贪心策略达到全局最优解。南京信息工程大学计算机与软件学
41、院586/11/2023 相比而言，动态规划则可以处理不具有贪心实相比而言，动态规划则可以处理不具有贪心实质的问题。质的问题。在用分治法解决问题时，由于子问题的在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大
42、量的重复候再找出已求得的答案，这样就可以避免大量的重复计算。计算。南京信息工程大学计算机与软件学院596/11/2023n由此而来的基本思路是，用一个表记录所有已解决的由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。被计算过，就将其结果填入表中。比较感性的说，比较感性的说，动态规划的思想是对贪心算法和分治法的一种折衷，动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有贪心实质，但是各个子问它所解决的问题往往不具有贪心实质，但是各个子问题又不是完全零散的，这
43、时候我们用一定的空间来换题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。取时间，就可以提高解题的效率。n 南京信息工程大学计算机与软件学院606/11/2023n二、动态规划的基本步骤二、动态规划的基本步骤 动态规划算法通常用于求解动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个
44、步骤进行：规划算法，通常可以按以下几个步骤进行：n（1 1）找出最优解的性质，并刻画其结构特征。）找出最优解的性质，并刻画其结构特征。n（2 2）递归地定义最优值。）递归地定义最优值。n（3 3）以自底向上的方式计算出最优值。）以自底向上的方式计算出最优值。n（4 4）根据计算最优值时得到的信息，构造一个最优解。）根据计算最优值时得到的信息，构造一个最优解。其中（其中（1）-（3）步是动态规划算法的基本步骤。在只需要求出最优值的）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行）可以省去。若需要求出问题的一个最优解，则
45、必须执行步骤（步骤（4）。此时，在步骤（）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，）中计算最优值时，通常需记录更多的信息，以便在步骤（以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。）中，根据所记录的信息，快速构造出一个最优解。南京信息工程大学计算机与软件学院616/11/2023关于“算法算法”的总结1n程序=数据结构+算法。（瑞士 N沃思）n面向对象程序设计强调的是数据结构n面向过程的程序设计语言主要关注的是算法。南京信息工程大学计算机与软件学院626/11/2023关于“算法算法”的总结2n程序设计的关键之一，是解题的方法与步骤，是算法。n学习高级语言的重点
46、，就是掌握分析问题、解决问题的方法，就是锻炼分析、分解，最终归纳整理出算法的能力。n具体语言的语法是工具，是算法的一个具体实现。南京信息工程大学计算机与软件学院636/11/2023关于“算法算法”的总结3n在高级语言的学习中，n一方面应熟练掌握该语言的语法，因为它是算法实现的基础；n另一方面必须认识到算法的重要性，加强思维训练，以写出高质量的程序。南京信息工程大学计算机与软件学院646/11/2023关于“算法算法”的总结4n算法就是解决问题方法的精确描述。但并不是所有问题都有算法，有些问题经研究，认为“可解”，则相应有算法，但这并不是说问题就有结果。n算法具有以下5个特征：确定性、能行性、
47、输入、输出和有穷性。n一个算法的描述通常有以下几种方式：用自然语言描述算法、流程图、N-S图、PAD、伪代码。南京信息工程大学计算机与软件学院656/11/2023关于“算法算法”的总结5n当分析一个算法时，首先就应确定算法的正确性。n算法的正确性是可以证明的。n但是要想证明一个复杂算法的正确性是一件极为耗时的工作。对于那些大型的，比较复杂的程序，为了证明它的正确性，我们可以先把这个程序分解成一些较小的程序段，分别进行验证。n要对一个算法的正确性进行严格的证明，最有用的技术之一就是数学归纳法。南京信息工程大学计算机与软件学院666/11/2023关于“算法算法”的总结6n对算法的评价可以有各种
48、标准，如易读性、易修改、易排错等，它们都属于结构化程序设计的讨论范畴；在算法分析中，主要研究的则是算法运行时所需要的时间和占用的空间，也就是算法的复杂度。在学习算法设计时，不仅要学习算法设计的技巧，更要研究算法对时间和空间的需求。南京信息工程大学计算机与软件学院676/11/2023关于“算法算法”的总结7n对于一些问题，如图的着色、逾期罚款的作业调度、装箱问题、背包问题、哈密尔顿路与哈密尔顿回路等，迄今为止都没有设计出一个具有合理的运行时间的算法。P问题是一类包含具有合理的有效率的算法的问题。还有一类问题称为NP类问题。当且仅当一个问题能用不确定算法在多项式时间内解答时该问题属于NP。对于NP类中最难以解决的问题，可以用NP-完全来描述。南京信息工程大学计算机与软件学院686/11/2023关于“算法算法”的总结8n算法设计的方法主要有：n穷举法（枚举法）、动态规划法、回溯法、贪婪法、分治法、分支限界法等。
