算法设计与分析 第6章 动态规划法

1、第六章第六章 动态规划法动态规划法1234概述概述图问题中的动态规划法图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法5查找问题中的动态规划法查找问题中的动态规划法小结小结五个海盗抢了一百颗钻石，每颗都价值连城。五个海盗抢了一百颗钻石，每颗都价值连城。五个海盗都很贪婪，他们都希望自己能分得最五个海盗都很贪婪，他们都希望自己能分得最多的钻石，但同时又都很明智。于是他们按照多的钻石，但同时又都很明智。于是他们按照抽签的方法排出一个次序。首先由抽到一号签抽签的方法排出一个次序。首先由抽到一号签的海盗说出一套分钻石的方案，如果的海盗说出一套分钻石的方案，如果5个人中个人中有有50（或以

2、上）的人同意，那么便依照这个（或以上）的人同意，那么便依照这个方案执行，否则的话，这个提出方案的人将被方案执行，否则的话，这个提出方案的人将被扔到海里喂鱼，接下来再由抽到二号签的海盗扔到海里喂鱼，接下来再由抽到二号签的海盗继续说出一套方案，然后依次类推到第五个。继续说出一套方案，然后依次类推到第五个。记住，五个海盗都很聪明哦！记住，五个海盗都很聪明哦！海盗分钻石问题海盗分钻石问题你想到了什么？你想到了什么？历史及研究问题历史及研究问题动态规划是运筹学的一个分支，动态规划是运筹学的一个分支，20世纪世纪50年代年代初美国数学家初美国数学家Bellman等人在研究等人在研究多阶段决策过多阶段决策过

3、程的优化问题程的优化问题时，提出了著名的最优性原理，创时，提出了著名的最优性原理，创立了解决这类过程优化问题的新方法立了解决这类过程优化问题的新方法动态规动态规划法。划法。多阶段决策问题：求解的问题可以划分为一系多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，每个阶段都需要做出决策，列相互联系的阶段，每个阶段都需要做出决策，而且一个阶段决策的选择会影响下一个阶段的决而且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策是整个过程达到最优。是选择各个阶段的决策是整个过程达到最优。动态规划主要用于

4、求解以时间划分阶段的动态动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。用动态规划方法方便地求解。动态规划是考察问题的一种途径，或是求解某动态规划是考察问题的一种途径，或是求解某类问题的一种方法。类问题的一种方法。动态规划问世以来，在经济管理、生产调度、动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的

5、应用。工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法排序、装载等问题，用动态规划方法比其它方法求解更为方便。求解更为方便。历史及研究问题历史及研究问题概概 述述多阶段决策过程多阶段决策过程当某问题有当某问题有n个输入，问题的解由这个输入，问题的解由这n个输入个输入的一个子集组成，这个子集必须满足某些事的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为先给定的条件，这些条件称为约束条件约束条件，满，满足约束条件的解称为问题的足约束条件的解称为问题的可行解可行

6、解。满足约。满足约束条件的可行解可能不只一个，为了衡量这束条件的可行解可能不只一个，为了衡量这些可行解的优劣，通常以函数的形式给出一些可行解的优劣，通常以函数的形式给出一定的标准，这些标准函数称为定的标准，这些标准函数称为目标函数目标函数（或（或评价函数），使目标函数取得极值（极大或评价函数），使目标函数取得极值（极大或极小）的可行解称为极小）的可行解称为最优解最优解，这类问题称为，这类问题称为最优化问题最优化问题 。概概 述述多阶段决策过程多阶段决策过程在在0/1背包问题中，物品背包问题中，物品i或者被装入背包，或者或者被装入背包，或者不被装入背包，设不被装入背包，设xi表示物品表示物品i装

7、入背包的情况，装入背包的情况，则当则当xi=0时，表示物品时，表示物品i没有被装入背包，没有被装入背包，xi=1时，时，表示物品表示物品i被装入背包。根据问题的要求，有如被装入背包。根据问题的要求，有如下约束条件和目标函数：下约束条件和目标函数：)1 ( 1 , 01nixCxwiniiiniiixv1max付款问题：付款问题：超市的自动柜员机（超市的自动柜员机（POS机）要找给机）要找给顾客数量最少的现金。顾客数量最少的现金。假定假定POS机中有机中有n张面值为张面值为pi(1in)的货币，用集的货币，用集合合P=p1, p2, , pn表示，若表示，若POS机需支付的现金机需支付的现金为为

8、A，则必须从，则必须从P中选取一个最小子集中选取一个最小子集S，使得，使得 （式（式6.1）miiiSmApSp1|)|(,SpSpxiii01如果用向量如果用向量X=( ( x1, x2, , xn) )表示表示S中所选取的货中所选取的货币，则币，则 （式（式6.2） 最优化问题最优化问题 则，则，POS机支付的现金必须满足机支付的现金必须满足 （式（式6.3）Apxniii 1niixd1min集合集合P是该问题的输入，满足式是该问题的输入，满足式6.1的解称为的解称为可行可行解解，式，式6.2是是解的表现形式解的表现形式，因向量，因向量X中有中有n个元个元素，每个元素的取值为素，每个元素

9、的取值为0或或1，所有这些向量的全，所有这些向量的全体构成该问题的体构成该问题的解空间解空间，式，式6.3是该问题的约束是该问题的约束条件，式条件，式6.4是该是该问题的目标函数问题的目标函数，使式，使式6.4取得取得极小值的解称为该极小值的解称为该问题的最优解。问题的最优解。 并且并且 （式（式6.4） 最优化问题最优化问题 最优性原理最优性原理 状态：表示每个阶段开始时，问题或系统所处的状态：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一客观状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。个阶段的某个终点。通常一个阶段有

10、若干个状态。 状态无后效性：如果某个阶段状态给定后，则该状态无后效性：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的阶段以后过程的发展不受该阶段以前各阶段状态的影响，也就是说状态具有马尔科夫性。影响，也就是说状态具有马尔科夫性。适于动态规划法求解的问题具有状态的无后效性适于动态规划法求解的问题具有状态的无后效性 策略：各个阶段决策确定后，就组成了一个决策策略：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到序列，该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程，其对应的某个策略称终止阶段的过程称为子过程，其对应的某个策略称

11、为子策略。为子策略。最优性原理最优性原理 具有具有n个输入的最优化问题，其求解过程划分为个输入的最优化问题，其求解过程划分为若干个阶段，每一阶段的决策仅依赖于前一阶段若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。成为下一阶段决策的依据。一个决策序列在不断变化的状态中产生。这个决一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。策序列产生的过程称为多阶段决策过程。 S0P1P2PnS1S2Sn-1Sn最优性原理最优性原理：无论决策过程的初始状态和初始：无论决策过程的

12、初始状态和初始决策如何，其余的决策都必须相对于初始决策决策如何，其余的决策都必须相对于初始决策所产生的当前状态，构成一个所产生的当前状态，构成一个最优决策序列最优决策序列。换言之，在多阶段决策中，各子问题的解只与换言之，在多阶段决策中，各子问题的解只与它前面的子问题的解相关，而且各子问题的解它前面的子问题的解相关，而且各子问题的解都是相对于当前状态的最优解，整个问题的最都是相对于当前状态的最优解，整个问题的最优解是由各个子问题的最优解构成。如果一个优解是由各个子问题的最优解构成。如果一个问题满足最优性原理通常称此问题具有问题满足最优性原理通常称此问题具有最优子最优子结构性质。结构性质。 最优性

13、原理最优性原理 ABCDE原问题原问题E的解依赖于子问题的解依赖于子问题C和和D的解，子问题的解，子问题D的解依赖于子问题的解依赖于子问题C和和B的解，子问题的解，子问题C的解的解依赖于子问题依赖于子问题A和和B的解，子问题的解，子问题B的解依赖于的解依赖于子问题子问题A的解，因此，动态规划的求解过程从的解，因此，动态规划的求解过程从初始子问题初始子问题A开始，逐步求解并记录各子问题开始，逐步求解并记录各子问题的解，直至得到原问题的解，直至得到原问题E的解。的解。最优性原理最优性原理 u最优性原理表明，一个最优问题的任何实例最优性原理表明，一个最优问题的任何实例的最优解是由该实例的子实例的最优

14、解组成。的最优解是由该实例的子实例的最优解组成。u一般来说，如果所求解问题对于最优性原理一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问的递题。而解决问题的关键在于获取各阶段问的递推关系式。推关系式。最优性原理最优性原理 动态规划法的设计思想动态规划法的设计思想 动态规划法将待求解问题分解成若干个相互重叠动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题一般来说，子问题

15、的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。决的子问题的解，这就是动态规划法的设计思想。具体的动态规划法是多种多样的，但他们具有相具体的动态规划法是多种多

16、样的，但他们具有相同的填表形式。同的填表形式。原问题的解原问题的解原问题原问题 填填 表表子问题子问题1子问题子问题2子问题子问题n动态规划法的设计思想动态规划法的设计思想 （1）划分子问题：将原问题分解为若干个子问题，）划分子问题：将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具每个子问题对应一个决策阶段，并且子问题之间具有重叠关系；有重叠关系；（2）确定动态规划函数：根据子问题之间的重叠）确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式（即动态规划函关系找到子问题满足的递推关系式（即动态规划函数），这是动态规划法的关键；数），这是动态规划法的关键

17、；（3）填写表格：设计表格，以自底向上的方式计）填写表格：设计表格，以自底向上的方式计算各个子问题的解并填表，实现动态规划过程。算各个子问题的解并填表，实现动态规划过程。动态规划法的求解过程动态规划法的求解过程一个简单的例子一个简单的例子数塔问题数塔问题问题描述：从数塔的顶层出发，在每一问题描述：从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得走到最底层，要求找出一条路径，使得路径上的数值和最大。路径上的数值和最大。 8123915681051291018416数塔问题数塔问题想法想法8123915681051291

18、018416数塔问题数塔问题想法想法求解初始子问题：底层的每个数字可以看作求解初始子问题：底层的每个数字可以看作1层数塔，则最大数值和层数塔，则最大数值和就是其自身；就是其自身；再求解下一阶段的子问题：第再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行层的决策是在底层决策的基础上进行求解，可以看作求解，可以看作4个个2层数塔，对每个数塔进行求解；层数塔，对每个数塔进行求解；再求解下一阶段的子问题：第再求解下一阶段的子问题：第3层的决策是在第层的决策是在第4层决策的基础上进层决策的基础上进行求解，可以看作行求解，可以看作3个个2层的数塔，对每个数塔进行求解；层的数塔，对每个数塔进行求

19、解；以此类推，直到最后一个阶段：第以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整层的决策结果就是数塔问题的整体最优解。体最优解。1. 初始化数组初始化数组maxAdd的最后一行为数塔的底层数据：的最后一行为数塔的底层数据： for (j = 0; j n; j+) maxAddn-1j = dn-1j;2. 从第从第n-1层开始直到第层开始直到第 1 层对下三角元素层对下三角元素maxAddij执行下述操作执行下述操作： 2.1 maxAddij = dij + maxmaxAddi+1j, maxAddi+1j+1； 2.2 如果选择下标如果选择下标j的元素的元素，则则path

20、ij = j， 否则否则pathij = j+1；3. 输出最大数值和输出最大数值和maxAdd00；4. 根据根据path数组确定每一层决策的列下标，输出路径数组确定每一层决策的列下标，输出路径信息；信息；数塔问题数塔问题算法算法图问题中的动态规划法图问题中的动态规划法多段图最短路径多段图最短路径 问题描述：设图问题描述：设图G=(V, E)是一个带权有向图，如果把顶点是一个带权有向图，如果把顶点集合集合V划分成划分成k个互不相交的子集个互不相交的子集Vi (2kn, 1ik)，使得，使得E中的任何一条边中的任何一条边(u, v)，必有，必有uVi，vVi+m (1ik, 1i+mk)，则称

21、图，则称图G为多段图，称为多段图，称sV1为源点，为源点，tVk为终为终点。多段图的最短路径问题求从源点到终点的最小代价点。多段图的最短路径问题求从源点到终点的最小代价路径。路径。2120345678949387684756866537W先生每天驾车去公司上班。先生每天驾车去公司上班。W先生的住所位于先生的住所位于A，公司位于，公司位于F，图中的直线段代表公路，交叉点，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在均行驶时间。现在W先生的问题是要确定一条最先生的问题是要确定一条最省时的上班路线。省时的上班路线。多

22、段图最短路径多段图最短路径实例实例 多段图最短路径多段图最短路径想法想法 由于多段图将顶点划分为由于多段图将顶点划分为k个互不相交的子集，所以，可个互不相交的子集，所以，可以将多段图划分为以将多段图划分为k段，每一段包含顶点的一个子集，根段，每一段包含顶点的一个子集，根据多段图的定义，每个子集中的顶点互不邻接。不失一据多段图的定义，每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的顺序无关紧要。假设图中的顶点个数为内顶点的顺序无关紧要。假设图中的顶点个数为n，则源，则源点点s的编号为的编号为0，终点，终点t的

23、编号为的编号为n-1，并且对图中的任何一，并且对图中的任何一条边条边，顶点，顶点u的编号小于顶点的编号小于顶点v的编号。的编号。 设设cuv表示多段图的有向边表示多段图的有向边上的权值，将从源点上的权值，将从源点s到到终点终点t的最短路径长度记为的最短路径长度记为d(s, t)，考虑原问题的部分解，考虑原问题的部分解d(s, v)，显然有下式成立：，显然有下式成立：d(s, v) =csv （E）d(s, v) = mind(s, u) + cuv （E）证明多段图的最短路径问题满足最优性原理。证明多段图的最短路径问题满足最优性原理。 首先求解初始子问题，可直接获得：首先求解初始子问题，可直接

24、获得：d(0, 1)=c014(01)d(0, 2)=c022(02)d(0, 3)=c033(03)再求解下一个阶段的子问题，有：再求解下一个阶段的子问题，有：d(0, 4)=mind(0, 1)+c14, d(0, 2)+c24=min4+9, 2+6=8(24)d(0, 5)=mind(0, 1)+c15, d(0, 2)+c25, d(0, 3)+c35=min4+8, 2+7, 3+4 =7(35)d(0, 6)=mind(0, 2)+c26, d(0, 3)+c36=min2+8, 3+7=10(26)再求解下一个阶段的子问题，有：再求解下一个阶段的子问题，有：d(0, 7)=mi

25、nd(0, 4)+c47, d(0, 5)+c57, d(0, 6)+c67=min8+5, 7+8, 10+6 =13(47)d(0, 8)=mind(0, 4)+c48, d(0, 5)+c58, d(0, 6)+c68=min8+6, 7+6, 10+5 =13(58)直到最后一个阶段，有：直到最后一个阶段，有：d(0, 9)=mind(0, 7)+c79, d(0, 8)+c89=min13+7, 13+3=16(89)再将状态进行回溯，得到最短路径再将状态进行回溯，得到最短路径03589，最短路径长度，最短路径长度16。多段图最短路径实例求解过程多段图最短路径实例求解过程 21203

26、45678949387684756866537多段图最短路径实例求解过程多段图最短路径实例求解过程 多段图最短路径问题的填表过程多段图最短路径问题的填表过程算法算法6.2：多段图的最短路径问题多段图的最短路径问题输入：多段图的代价矩阵输入：多段图的代价矩阵输出：最短路径长度及路径输出：最短路径长度及路径1. 循环变量循环变量j从从1n-1重复下述操作，执行填表工作：重复下述操作，执行填表工作： 1.1 考察顶点考察顶点j的所有入边，对于边的所有入边，对于边(i, j)E： 1.1.1 costj=mincosti+cij; 1.1.2 pathj=使使costi+cij最小的最小的i; 1.2

27、 j+;2. 输出最短路径长度输出最短路径长度costn-1;3. 循环变量循环变量i=pathn-1，循环直到，循环直到pathi=0： 3.1 输出输出pathi; 3.2 i=pathi;多段图最短路径多段图最短路径算法算法 图问题中的动态规划法图问题中的动态规划法 TSP TSP问题问题 TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市个城市,要求各个城市经历且仅经历一次然要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路后回到出发城市，并要求所走的路程最短。程最短。TSPTSP问题问题 想法想法TSP问题满足最优性原理。问题满足最优性原理。对于图对于图G=(V, E)

28、，假设从顶点，假设从顶点i出发，令出发，令V=V-i，则则d(i, V)表示从顶点表示从顶点i出发经过出发经过V中各个顶点一次中各个顶点一次且仅一次，最后回到出发点且仅一次，最后回到出发点i的最短路径长度，的最短路径长度， 显然，初始子问题是显然，初始子问题是d(k, )，即从顶点，即从顶点i出发只出发只经过顶点经过顶点k回到顶点回到顶点i。现在考虑原问题的一部分，。现在考虑原问题的一部分，d(k, V-k)表示从顶点表示从顶点k出发经过出发经过V-k中各个顶中各个顶点一次且仅一次，最后回到出发点点一次且仅一次，最后回到出发点i的最短路径的最短路径长度，则：长度，则：d(k, )=ckid(i

29、, V)=mincik + d(k, V-k)（kV）首先计算初始子问题，可以直接获得：首先计算初始子问题，可以直接获得：d(1, )= c10 =5(10);d(2, )= c20 =6(20);d(3, )= c30 =3(30)再求解下一个阶段的子问题，有：再求解下一个阶段的子问题，有：d(1, 2)= c12+d(2, )=2+6=8(12); d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 1)= c21+d(1, )=4+5=9(21); d(2, 3)= c23+d(3, )=2+3=5(23) d(3, 1)= c31+d(1, )=7+5=12(31);

30、d(3, 2)= c32+d(2, )=5+6=11(32)再求解下一个阶段的子问题，有：再求解下一个阶段的子问题，有：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32)直到最后一个阶段，有：直到最后一个阶段，有：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2,

31、 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01)所以，从顶点所以，从顶点0出发的出发的TSP问题的最短路径长度为问题的最短路径长度为10，再将状态进行回溯，得，再将状态进行回溯，得到最短路径是到最短路径是01230。TSPTSP问题问题 实例实例 3 6 7 5 2 3 6 4 2 3 7 5 出发点 1231, 2 1, 3 2, 31, 2, 3010011510812613712262092152310213330123111321432TSPTSP问题问题 实例（填表过程）实例（填表过程）TSPTSP问题问题 算法算法TSP问题问题输

32、入：图的代价矩阵输入：图的代价矩阵arcnn输出：从顶点输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度的最短路径长度 1. 初始化第初始化第0列：列： for (i=1; in; i+) di0=ci0; 2. 依次处理每一个子集数组依次处理每一个子集数组V2n-1 for (i=1; in; i+) if (子集子集Vj中不包含中不包含i) 对对Vj中的每个元素中的每个元素k， 计算计算dij=minarcik+dkj- -1; 3. 输出最短路径长度输出最短路径长度d02n-1- -1;组合问题中的动态规划法组合问题中的动态规划法

33、 最长递增子序列问题最长递增子序列问题 问题描述：在数字序列问题描述：在数字序列A=a1, a2, , an中按递增中按递增下标序列下标序列(i1, i2, ik)（1i1 i2 ikn）顺序选）顺序选出一个子序列出一个子序列B，如果子序列，如果子序列B中的数字都是严格中的数字都是严格递增的，则子序列递增的，则子序列B称为序列称为序列A的递增子序列。最的递增子序列。最长递增子序列问题就是要找出序列长递增子序列问题就是要找出序列A的一个最长的一个最长的递增子序列。的递增子序列。最长递增子序列问题最长递增子序列问题想法想法设序列设序列A=a1, a2, , an最长递增子序列是最长递增子序列是B=

34、b1, b2, bm最长递增子序列问题满足最优性原理。最长递增子序列问题满足最优性原理。 设设L(n)为数字序列为数字序列A=a1, a2, , an的最长递增子的最长递增子序列的长度，显然，初始子问题是序列的长度，显然，初始子问题是a1，即，即L(1)=1。考虑原问题的一部分，设考虑原问题的一部分，设L(i)为子序列为子序列A=a1, a2, , ai的最长递增子序列的长度，则满足如下的最长递增子序列的长度，则满足如下递推式：递推式： 1 i = 1或不存在或不存在ajai（1ji）maxL(j) + 1 对于所有的对于所有的ajai（1ji）L(i) =于序列于序列A=5, 2, 8, 6

35、, 3, 6, 9, 7，用动态规划法求，用动态规划法求解最长递增子序列。解最长递增子序列。最长递增子序列问题最长递增子序列问题实例实例首先计算初始子问题，可以直接获得：首先计算初始子问题，可以直接获得：L(1)=1(5)然后依次求解下一个阶段的子问题，有：然后依次求解下一个阶段的子问题，有：L(2)=1(2)L(3)=maxL(1)+1, L(2)+1=2(5, 8, 2, 8)L(4)= maxL(1)+1, L(2)+1=2(5, 6, 2, 6)L(5)=L(2)+1=2(2, 3)L(6)=maxL(1)+1, L(2)+1, L(5)+1)=3(2, 3, 6)L(7)=maxL(

36、1)+1, L(2)+1, L(3)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 9)L(8)=maxL(1)+1, L(2)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 7)序列序列A的最长递增子序列的长度为的最长递增子序列的长度为4，有两个最长递增子序列，分别是，有两个最长递增子序列，分别是2, 3, 6, 9和和2, 3, 6, 7)。最长递增子序列问题最长递增子序列问题实例（填表）实例（填表）序号序号12345678序列序列元素元素52863697子序子序列长列长度度11222344递增递增子序子序列列525,8,2,85,6

37、,2,62,32,3,6 2,3,6,92,3,6,7最长递增子序列问题最长递增子序列问题算法算法设序列设序列A存储在数组存储在数组an中，数组中，数组Ln存储最存储最长递增子序列的长度，其中长递增子序列的长度，其中Li表示元素序列表示元素序列a0ai的最长递增子序列的长度，二维数组的最长递增子序列的长度，二维数组xnn存储对应的最长递增子序列，其中存储对应的最长递增子序列，其中xin存储存储a0ai的最长递增子序列，注意的最长递增子序列，注意到数组下标均从到数组下标均从0开始，给出用开始，给出用C+语言描述语言描述的算法。的算法。组合问题中的动态规划法组合问题中的动态规划法 最长公共子序列问

38、题最长公共子序列问题问题描述：对给定序列问题描述：对给定序列X=(x1, x2, xm)和序列和序列Z=(z1, z2, zk)，Z是是X的子序列当且仅当存在一个的子序列当且仅当存在一个递增下标序列递增下标序列(i1, i2, ik)，使得对于所有，使得对于所有j=1, 2, , k，有（，有（1ijm）。）。给定两个序列给定两个序列X和和Y，当序列，当序列Z既是既是X的子序列又是的子序列又是Y的子序列时，称的子序列时，称Z是序列是序列X和和Y的公共子序列最长的公共子序列最长公共子序列问题就是在序列公共子序列问题就是在序列X和和Y中查找最长的公中查找最长的公共子序列。共子序列。 设序列设序列X

39、=x1, x2, xm，Y=y1, y2, yn最长公共子序列为最长公共子序列为Z=z1, z2, zk最长公共子序列问题满足最优性原理。最长公共子序列问题满足最优性原理。 设设L(m, n)表示序列表示序列X=x1, x2, xm和和Y=y1, y2, yn的最的最长公共子序列的长度，显然，初始子问题是序列长公共子序列的长度，显然，初始子问题是序列X和和Y至少至少有一个空序列，即：有一个空序列，即：L(0, 0)=L(0, j)=L(i, 0)=0 (1im, 1jn)(1,1) 1,1,1( , )max ( ,1), (1, ),1,1ijijL ijxy ijL i jL i jL i

40、jxy ij设设L(i, j)表示子序列表示子序列Xi和和Yj的最长公共子序列的长度，则有的最长公共子序列的长度，则有如下动态规划函数：如下动态规划函数： 最长公共子序列问题最长公共子序列问题想法想法最长公共子序列问题最长公共子序列问题实例实例序列序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，动态规，动态规划法求解最长公共子序列。划法求解最长公共子序列。1( , )2( ,1)(1, )3( ,1)(1, )ijijijxyS i jxyL i jL ijxyL i jL ij且且设二维表设二维表S(m, n)记载求解过程中的状态变化

41、，其中记载求解过程中的状态变化，其中S(i, j)表示在计算表示在计算L(i, j)时的搜索状态，并且有：时的搜索状态，并且有：若若S(i, j)=1，表明，表明xi=yj，则下一个搜索方向是，则下一个搜索方向是S(i-1,j-1)；若若S(i, j)=2，表明，表明xiyj且且L(i, j-1)L(i-1, j)，则下一个搜索，则下一个搜索方向是方向是S(i, j-1)；若；若S(i, j)=3，表明，表明xiyj且且L(i, j-1)L(i-1, j)，则下一个搜索方向是，则下一个搜索方向是S(i-1, j)。最长公共子序列问题最长公共子序列问题实例（填表）实例（填表）最长公共子序列问题最

42、长公共子序列问题算法算法int CommonOrder(char x , int m, char y , int n, char z ) int i, j, k; for (j = 0; j = n; j+) L0j = 0; for (i = 0; i = m; i+) Li0=0; for (i = 1; i = m; i+) for (j = 1; j = Li-1j) Lij = Lij-1; Sij = 2; else Lij = Li-1j; Sij = 3; 最长公共子序列问题最长公共子序列问题算法算法 i = m; j = n; k = Lmn; while (i 0 & j

43、0) if (Sij = 1) zk = xi; k-; i-; j-; else if (Sij = 2) j-; else i-; for (k = 0; k Lmn; k+) coutV(n-1,C)，表明第，表明第n个物品被装入背包，前个物品被装入背包，前n-1个个物品被装入容量为物品被装入容量为C-wn的背包中；否则，第的背包中；否则，第n个物品没有个物品没有被装入背包，前被装入背包，前n-1个物品被装入容量为个物品被装入容量为C的背包中。依的背包中。依此类推，直到确定第此类推，直到确定第1个物品是否被装入背包中为止。由个物品是否被装入背包中为止。由此，得到如下函数：此，得到如下函数：), 1(),(, 1),