计算理论与算法12年CH3动规

1、2021-12-141动态规划法动态规划法 2021-12-142方法概述: 发展及研究内容n动态规划(dynamic programming)是运筹学的一个分是运筹学的一个分支，支，20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人等人在研究在研究多阶段决策过程(multistep decision process)的的优化问题时，提出了著名的时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问问题，逐个求解，创立了解决这类过程优化问题的新方

2、法题的新方法动态规划。动态规划。n动态规划问世以来，在经济管理、生产调度、动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了工程技术和最优控制等方面得到了广泛的应用广泛的应用。例如最短路线、资源分配、设备更新等问题，例如最短路线、资源分配、设备更新等问题，用动态规划比用其它方法求解更为方便。用动态规划比用其它方法求解更为方便。2021-12-143方法概述: 基本思想 n动态规划的思想实质是动态规划的思想实质是分治思想和和解决冗余。 n与分治法类似的是，将原问题分解成若干个子问题，与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的先

3、求解子问题，然后从这些子问题的解得到原问题的解。解。n与分治法不同的是，经分解的子问题往往不是互相独与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。子问题）被重复计算了很多次。n如果能够保存已解决的子问题的答案，在需要时再查如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间。动态规划找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。法用一个表来记录所有已解的子问题的答案。n这就是动态规划法的基本思路。具体的动态

4、规划算法这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。多种多样，但它们具有相同的填表方式。2021-12-144方法概述: 求解步骤 1、找出最优解的性质，并刻画其结构特征；、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；、以自底向上的方式计算出最优值；4、根据计算最优值时记录的信息，构造最优解。、根据计算最优值时记录的信息，构造最优解。注：注：步骤步骤1-3是动态规划算法的基本步骤。在只需要是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤求出最

5、优值的情形，步骤4可以省略；可以省略；若需要求出问题的一个最优解，则必须执行步若需要求出问题的一个最优解，则必须执行步骤骤4，步骤，步骤3中记录的信息是构造最优解的基础中记录的信息是构造最优解的基础2021-12-145方法概述: 适用条件 动态规划法的有效性依赖于问题本身所具有的动态规划法的有效性依赖于问题本身所具有的两个重要性质两个重要性质n最优子结构最优子结构：当问题的最优解包含了其子问题：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。的最优解时，称该问题具有最优子结构性质。n重叠子问题重叠子问题：在用递归算法自顶向下解问题时，：在用递归算法自顶向下解问题时，每次产

6、生的子问题并不总是新问题，有些子问每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。尽可能多地利用这些子问题的解。2021-12-146方法概述: 最优性原理及举例 nBellman给出这个原理作为动态规划的适用条给出这个原理作为动态规划的适用条件，后来件，后来Morin在在19821982年证明了这只是一个充年证明了这只是一个充分条件而

7、非必要条件。分条件而非必要条件。Bellman的原定义如下：的原定义如下：n An optimal policy has the property that whatever the initial state and initial decision are, then remaining decisions must constitute an optimal policy with regard to the state resulting from first decision. n最优性原理又称为最优子结构性质最优性原理又称为最优子结构性质：n 如果有一决策序列包含有非最优的决策子序

8、列，则该决如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。即一个最优策略的子策略总是最策序列一定不是最优的。即一个最优策略的子策略总是最优的。优的。2021-12-147l例例1：多段图的最短路问题：多段图的最短路问题多段图：设多段图：设G=是一个有向连通图，是一个有向连通图，其中其中|V|=n, |E|=m, V有划分有划分V1,V2,Vk，这里这里V1 =s,s称为源点，称为源点， Vk =t,t称为称为终点，其中终点，其中k 2 。对于每条有向边。对于每条有向边 E都存在都存在Vi V，使得，使得u Vi和和v Vi+1, 其中其中1ik且每条边且每条边均均附有代价

9、附有代价C(u,v)，则称，则称G是一个是一个k段图。段图。2021-12-148123456789101112s97324212711118654356425V1V2V3V4V5t2021-12-149l最短路：从源点最短路：从源点s到终点到终点t的整条路上的的整条路上的代价之和为最小。代价之和为最小。每个子集每个子集Vi构成图中的一段。由于构成图中的一段。由于E的的约束，每条从约束，每条从s到到t的路径都是从第一段的路径都是从第一段开始，然后顺次经过第开始，然后顺次经过第2段，第段，第3段，段，最后在第最后在第k段终止。对于每条从段终止。对于每条从s到到t的路的路径，可以把它看成在径，可以

10、把它看成在k-2个阶段中做出个阶段中做出的某个决策序列的相应结果。的某个决策序列的相应结果。2021-12-1410l假设假设s,v2,v3,vk-1,t是一条从是一条从s到到t的最短路径，的最短路径，还假定从源点还假定从源点s（初始状态）开始，已做出了到（初始状态）开始，已做出了到结点结点v2的决策（初始决策），因此的决策（初始决策），因此v2就是初始决就是初始决策所产生的状态。如果把策所产生的状态。如果把v2看成是原问题的一个看成是原问题的一个子问题的初始状态，解这个子问题就是找出一子问题的初始状态，解这个子问题就是找出一条由条由v2到到t的最短路径。这条路径显然是的最短路径。这条路径显然

11、是 v2,v3,vk-1,t，否则设，否则设v2,q3,qk-1,t是一条由是一条由v2到到t的更短路径，则的更短路径，则s,v2,q3,qk-1,t是一条比路径是一条比路径s,v2,v3,vk-1,t 更短的由更短的由s到到t的路径，与假设矛的路径，与假设矛盾，故最优化原理成立。盾，故最优化原理成立。 2021-12-1411cost(i,j)=minC(j,r)+cost(i+1,r) rVi+1 EjrtViVi+1最短最短最短最短向前处理法：设向前处理法：设P(i,j)是从是从Vi中的点中的点j到到t的一条最短路，的一条最短路，cost(i,j)是这条路线的是这条路线的耗费。由后向前推

12、算，得到耗费。由后向前推算，得到2021-12-1412123456789101112s97324212711118654356425V1V2V3V4V5tcost(4,9)=4cost(i,j)=minC(j,r)+cost(i+1,r) cost(4,10) =2 cost(4,11)=5cost(3,6)=min6+cost(4,9),5+cost(4,10)=min6+4,5+2=7从第从第3段的顶点段的顶点6到到t的最短路径是的最短路径是6-10-t5+22021-12-1413123456789101112s97324212711118654356425V1V2V3V4V5tcos

13、t(3,7)= min4+cost(4,9),3+cost(4,10) =min4+4,3+2=5从第从第3段的顶点段的顶点7到到t的最短路径是的最短路径是7-10-t cost(3,8)=7从第从第3段的顶点段的顶点8到到t的最短路径是的最短路径是8-10-t2021-12-1414123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7 从第从第2段顶点段顶点2到到t的最短路是的最短路是2-7-10-tcost(2,3)=9从第从第2段顶点段顶点3到到t的最短路是的最短路是3-6-10-tcost(2,4)=18从第从第2段

14、顶点段顶点4到到t的最短路是的最短路是4-8-10-tcost(2,5)=15从第从第2段顶点段顶点5到到t的最短路是的最短路是5-8-10-tcost(1,1)=16 从第从第1段顶点段顶点1到到t的最短路径由两条：的最短路径由两条： 1-2-7-10-t和和1-3-6-10-t2021-12-1415从从s到到t的一条最短路径的代价为的一条最短路径的代价为16。用用D(i,j)表示使表示使C(j,r)+cost(i+1,r)取得最小值取得最小值的的r，则在上述求解过程中同时得到：，则在上述求解过程中同时得到：D(3,6)=10, D(3,7)=10, D(3,8)=10D(2,2)=7,

15、D(2,3)=6, D(2,4)=8D(2,5)=8, D(1,1)=2设从设从s到到t的最短路径为的最短路径为s,w2,w3,wk-1,t则有则有w2=D(1,1)=2w3= D(2,D(1,1)=D(2,2)=7w4=D(3,D(2,D(1,1)=D(3,D(2,2)=D(3,7)=10所以这条路径是1-2-7-10-t所以这条路径是所以这条路径是1-2-7-10-t2021-12-1416为了便于描述算法，对一个为了便于描述算法，对一个k段图的顶点，段图的顶点，按段的顺序给它的每个顶点编号。设图中有按段的顺序给它的每个顶点编号。设图中有n个顶点，则编号为个顶点，则编号为1，2，n。首先，

16、给。首先，给s编为编为1号；然后给号；然后给V2中的各个顶点分别编为中的各个顶点分别编为2，3， ，| V2 |+1号；以此类推，最后号；以此类推，最后t编号为编号为n。这样编号使这样编号使Vi+1中的任何顶点的编号大于中的任何顶点的编号大于Vi中中所有顶点的编号。所有顶点的编号。于是，可以按于是，可以按n-1,n-2,1的顺序计算出的顺序计算出cost(i,j)和和D(i,j)。算法中可以利用顺序编号。算法中可以利用顺序编号的特点，而不再考虑顶点所在的段。的特点，而不再考虑顶点所在的段。2021-12-1417设顶点的编号已知，边已知及边的代价函设顶点的编号已知，边已知及边的代价函数数C(i

17、,j)已知。用已知。用costi表示顶点表示顶点i到到t的最小的最小代价，代价， 1i n。用。用Di表示从顶点表示从顶点i到到t的最的最短路径上顶点短路径上顶点i的后继顶点号，用的后继顶点号，用Pi表示表示最短路径经过第最短路径经过第i级的顶点号，级的顶点号， 1i k2021-12-1418求两点间最短路径的算法：求两点间最短路径的算法：Procedure Fgraph1. for i 1 to n costi 0；2. for j =n-1 step 1 to 1 do 3. 找顶点找顶点r,使使 E,且且C(j,r)+costr最小；最小；4. costjC(j,r)+costr;5.

18、 Dj r ; 6. P1 1 ; Pk n;7. for j=2 to k-1 do Pj DPj-1 O(n+|E|)2021-12-1419123456789101112s97324212711118654356425V1V2V3V4V5t（从前）向后：设（从前）向后：设BPij是从源点是从源点s到到Vi中顶点中顶点j的最小成本路径，的最小成本路径，bcost(i,j)是这是这条路径的代价条路径的代价bcost(i,j)=minbcost(i-1,r) + C(r,j) r Vi-1 E2021-12-1420l格路问题：求从起点格路问题：求从起点O(0,0)到终点到终点E(m,n)的最

19、短路。则分别用穷举法和动态规划法的最短路。则分别用穷举法和动态规划法的加法次数和比较次数各是多少？的加法次数和比较次数各是多少？E(m,n)O(0,0)xy2021-12-1421E(m,n)O(0,0)xy2021-12-1422E(m,n)O(0,0)xymn个点个点 2021-12-1423l例例2：货郎担问题：货郎担问题12431052091289 13156810 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v42021-12-1424不失一般性，考虑以结点不失一般性，考虑以结点1为起点和终为起点和终点的一条哈密顿回路。每一条这样的路点的

20、一条哈密顿回路。每一条这样的路线都由一条边线都由一条边和一条由结点和一条由结点k到结到结点点1的路径组成，其中的路径组成，其中kV-1,而这条而这条由结点由结点k到结点到结点1的路径通过的路径通过V-1，k的的每个结点各一次。如果这条周游路线是每个结点各一次。如果这条周游路线是最优的，则这条由结点最优的，则这条由结点k到结点到结点1的路径的路径必定是通过必定是通过V-1，k的每个结点各一次的每个结点各一次的由的由k到到1的最短路径。的最短路径。2021-12-1425l设设T( i,S)是由结点是由结点 i出发，经过结点集出发，经过结点集S中中每个结点各一次并回到初始结点每个结点各一次并回到初

21、始结点1的一条最的一条最短路径长度，则短路径长度，则T(1,V-1)就是一条最优的就是一条最优的周游路线长度。动态规划模型：周游路线长度。动态规划模型：T(1,V-1)=mind1k+T(k,V-1,k)2 k n T( i,s)=mindij+T(j,S-j)j S,i S2021-12-1426 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v4T(1, 2,3,4)=mind12+T(2,3,4) , d13+T(3,2,4) , d14+T(4,2,3) T(2,3,4) =mind23+T(3,4) , d24+T(4,3)T(3,4) =

22、 d34+T(4,)T(4,)=d412021-12-1427T(1,2,3,4)T(2,3,4)T(3,2,4)T(4,2,3)T(3,4)T(4,3)T(2,4)T(4,2)T(2,3)T(3,2)T(4,)T(3,)T(4,)T(2,)T(3,)T(4,)2021-12-1428矩阵链乘法n问题描述问题描述n加括号的方案数加括号的方案数 n动态规划法动态规划法 2021-12-1429矩阵链乘法: 问题描述给定给定n个矩阵个矩阵A1,A2, An, Ai的维数为的维数为pi-1pi(1in), 要求计算链乘积要求计算链乘积A1A2 An由于矩阵乘法满足结合率，所以可以由于矩阵乘法满足结合

23、率，所以可以有许多不同的计算次序，这种计算次有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。序可以用加括号的方式来确定。比如： A1,A2,A3,A4 (A1 ( A2 ( A3 (A4) ) ) (A1 ( A2 A3 ) A4 ) ) (A1 A2 )( A3 A4 ) ( A1 ( A2 A3) ) A4 ) ( A1 A2 ) A3) A4 )2021-12-1430不同的计算次序有不同的计算量不同的计算次序有不同的计算量注：注：1.设设Apq,Aqr两矩阵相乘，普通乘法的次数两矩阵相乘，普通乘法的次数为为pqr2.加括号对乘法次数的影响加括号对乘法次数的影响 如：如：A1

24、0100B1005C550 (AB)C): 101005+10550=7500次次 (A(BC): 100550+1010050=75000次次2021-12-1431穷举法：穷举法： 将将n个矩阵从第个矩阵从第k和第和第k+1处隔开，对二个子序列处隔开，对二个子序列再分别加括号，则可以得到下面递归式：再分别加括号，则可以得到下面递归式：1111( )( ) ()1nknp np k p nkn因此，穷举法不是一个有效算法3/2( )(1)2414( )21np nC nCatalannC nnnn 为数呈指数增长2021-12-14321.矩阵链乘问题满足最优性原理 记Ai:j为AiAi+1

25、Aj链乘的一个最优括号方案，设Ai:j的最优次序中含有二个子链Ai:k和Ak+1:n，则Ai:k和Ak+1:n也是最优的。（反证可得）2.矩阵链乘的子问题空间：Ai:j, 1ijn A1:1, A1:2, A1,:3, , A1:n A2:2, A2:3, , A2:n An-1:n-1, An-1,n An,n 2021-12-1433l递归求解最优解的值 记mij为计算Ai:j的最少乘法数，则原问题的最优值为 m1njipppjkmkimminjijimjkijki110(AiAi+1Ak)pi-1pk(Ak+1Ak+2Aj)pkpj2021-12-1434依据递归式自底向上计算。在计算过

26、程中，保存已经解决的子问题答案。A1,A2,A3,A4,A5,A6jipppjkmkimminjijimjkijki1102021-12-1435A1=(a ij)35 40 A2=(a ij)40 20 A3 =(a ij)20 10 A4=(aij)10 15jipppjkmkimminjijimjkijki110m13 = min m12 =m23 =40 20 108000m34 =20 10 15300035 40 2028000m11+m23+ 35 4010 ,m12+m33+ 35 2010 m24m14m11m12m13m14m22m23m24m33m34m44 j= 1 2

27、 3 4i=1 2 3 42021-12-1436MATRIX-CHAIN-ORDER(p)1 n lengthp - 12 for i 1 to n3 do mi, i 04 for l 2 to n /l is the chain length.5 do for i 1 to n - l + 16 do j i + l - 17 mi, j 8 for k i to j - 19 do q mi, k + mk + 1, j + pi-1pkpj10 if q mi, j11 then mi, j q12 si, j k13 return m and s (n3)2021-12-1437矩

28、阵链乘法: s中存放中存放m取得最优时取得最优时k的值的值行行 x 列列A130 x35A235x15A315x5A4 5x10A510 x20A620 x256555443333i33322333111654321sj6543i21 6 54321mj0000001512550003500100053752500750105007125437526251187593757875157502021-12-1438矩阵链乘法: s中存放中存放m取得最优时取得最优时k的值的值6555443333i33322333111654321sjPRINT-OPTIMAL-PARENS(s, i, j)1 i

29、f i = j2 then print Ai3 else print (4 PRINT-OPTIMAL-PARENS(s, i, si, j)5 PRINT-OPTIMAL-PARENS(s, si, j + 1, j)6 print )A1,A2,A3,A4,A5,A6 (A1 (A2 A3) (A4 A5)A6) 2021-12-1439在一个铁路沿线顺序存放着在一个铁路沿线顺序存放着n堆装满货物的集装箱。堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的每次只能选相邻的2堆集装箱合并成新的一堆，所需堆集装箱合并

30、成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。的运输费用与新的一堆中集装箱数成正比。 给定各堆给定各堆的集装箱数，试制定一个运输方案，使总运输费用最的集装箱数，试制定一个运输方案，使总运输费用最少。少。5, 3, 4, 1, 3, 2, 3, 4 为了简化，只算为了简化，只算5, 3, 4, 1在一个圆形操场的四周存放着在一个圆形操场的四周存放着n堆装满货物的集装箱。堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的每次只能选相邻的2堆集装箱合并成新的一堆，所需堆集装箱合并成新的一堆，所需的运输费用与新的一堆

31、中集装箱数成正比。的运输费用与新的一堆中集装箱数成正比。 给定各堆给定各堆的集装箱数，试制定一个运输方案，使总运输费用最的集装箱数，试制定一个运输方案，使总运输费用最少。只要求给出思路。少。只要求给出思路。2021-12-1440在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,4设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，j

32、ijitajkmkimjimjitjki, 1,min0,jipppjkmkimminjijimjkijki1102021-12-14415, 3, 4, 1jijitajkmkimjimjitjki, 1,min0,m11m12m13m14m22m23m24m33m34m44 j = 1 2 3 4i = 1 2 3 4 j = 1 2 3 4i = 1 2 3 4反例反例4, 2, 3, 42021-12-1442最优子结构: 无后效性无权最短路径无权最短路径: 边数最少边数最少. 具有最优子结构性质具有最优子结构性质.无权最长最短路径无权最长最短路径: 一定简单一定简单. if we d

33、ecompose a longest simple path into subpaths , then mustnt p1 be a longest simple path from u to w, and mustnt p2 be a longest simple path from w to v?The answer is no! uv除接合点外除接合点外,不不能共享资源能共享资源.2021-12-1443最优子结构: 无后效性动态规划要求其子问题既独立又重叠动态规划要求其子问题既独立又重叠:如果同一问题的两个子问题不共享资源如果同一问题的两个子问题不共享资源,则它们则它们是是独立独立的的

34、; 对两个子问题来说对两个子问题来说,如果它们确实是相同的子问如果它们确实是相同的子问题题,只是作为不同问题的子问题出现的话只是作为不同问题的子问题出现的话,是重叠是重叠的的,则它们是则它们是重叠重叠的的.2021-12-1444重叠子问题对比分治法对比分治法 递归的每一步常常产生全新的子问题递归的每一步常常产生全新的子问题. 2021-12-1445计算m14过程如下：自顶向下递归求解最优解的值重叠子问题2021-12-1446备忘录MEMOIZED-MATRIX-CHAIN(p)1 n lengthp - 12 for i 1 to n3 do for j i to n4 do mi, j

35、 5 return LOOKUP-CHAIN(p, 1, n)/表示该子问题尚未解决表示该子问题尚未解决2021-12-1447备忘录LOOKUP-CHAIN(p, i, j)1 if mi, j 2 then return mi, j3 if i = j4 then mi, j 05 else for k i to j - 16 do q LOOKUP-CHAIN(p, i, k) + LOOKUP-CHAIN(p,k + 1, j) + pi-1 pk pj7 if q mi, j8 then mi, j q9 return mi, j2021-12-1448自底向上的动规与备忘录区别自底

36、向上的动规自底向上的动规每个子问题至少求解一次每个子问题至少求解一次.备忘录备忘录某些子问题根本没有必要求解某些子问题根本没有必要求解.2021-12-1449FloydA(k+1)(i, j) = minA(k)(i, j) , A(k)(i, k+1)+ A(k)(k+1, j) A(k)(i, j)表示从表示从i到到j的最短路径的最短路径,且允许的中且允许的中间结点是间结点是1 k0 4 11 6 0 2 3 0v1 v2v3v1 v2 v3123643112v1 v2v3v1 v2 v30 4 11 6 0 2 3 7 0A(1) =2021-12-1450A(k+1)(i, j) =

37、 minA(k)(i, j) , A(k)(i, k+1)+ A(k)(k+1, j) A(k)(i, j)表示从表示从i到到j的最短路径的最短路径,且允许的中且允许的中间结点是间结点是1 k0 4 11 6 0 2 3 0v1 v2v3v1 v2 v3123643112v1 v2v3v1 v2 v30 4 11 6 0 2 3 7 0A(1) =v1 v2v3v1 v2 v30 4 6 6 0 2 3 7 0A(2) =v1 v2v3v1 v2 v30 4 6 5 0 2 3 7 0A(3) =2021-12-1451 Mk+1i, j = Mki, jFloyd: A(k+1)(i, j)

38、 = minA(k)(i, j) , A(k)(i, k+1)+ A(k)(k+1, j) (Mki, k+1 Mkk+1, j)2021-12-1452 Mk+1i, j = Mki, j(Mki, k+1 Mkk+1, j)00 1 0 01 0 1 00 0 0 10 1 0 0M10 1 0 01 1 1 00 0 0 10 1 0 0M21 1 1 01 1 1 00 0 0 11 1 1 0M:Rabcd2021-12-1453TRANSITIVE-CLOSURE(G)1 n |VG|2 for i 1 to n3 do for j 1 to n4 do if i = j or (

39、i, j) EG11 return T (n) Warshall算法2021-12-14540-1背包问题:问题描述及举例 n问题描述问题描述n举例：举例：w=(w1,w2,w3)=(2,3,4), v=(v1,v2,v3)=(1,2,5), n=3, c=6, 求求Knap(1,3,6) 取取x=(1,0,1)时，时，使目标函数最大求定义如下：).,(1 , 000),(1nlliinliiiinliiixxxnilxwcxwvxvmaxcnlKnapniiixv16150211最大2021-12-1455n0-1背包问题满足最优性原理背包问题满足最优性原理n证明：设证明：设(y1,y2,y

40、n)是是Knap(1,n,c)的一个最优解，则的一个最优解，则n(y2,yn)是是Knap(2,n,c-w1y1)子问题的一个最优解。子问题的一个最优解。n若不然，设若不然，设(z2,zn)是是Knap(2,n,c-w1y1)的最优解，因此有的最优解，因此有),(1 ,0cnlKnapnilxcxwxvmaxinliiinliii记czwywyvzvyvywczwyvzvn2iiiniiin2iiin2iiin2iiin2iii又有且1111111说明(y1,z2,zn)是Knap(1,n,c)的一个更优解，矛盾。2021-12-14560-1背包问题: 递归关系 n考虑子问题：考虑子问题：

41、Knap(i, n, j) jc (假设假设c, wi取整数取整数) 设其最优值为设其最优值为m(i, j), 即即m(i, j)是背是背包容量为包容量为j, 可选物品为可选物品为i,i+1,n的的0-1背包问题的最优值。背包问题的最优值。子问题的背包容量在变化),(1 , 0wvmaxnikknkjniKnapnkixjxxkkikk记2021-12-14570-1背包问题: 递归关系 n递归式如下：递归式如下：不取物品i取物品iiiiiiiiiwjpwjoptpjoptpwjjoptpjoptp)(),(max)()(1110)()0(0joptpoptpi2021-12-14580-1背

42、包问题: 算法 void Knapsack(int v, int w, int c, int n, int m)/输出输出m1c int jMax=min(wn-1, c); /因为因为jc, 只要计算到只要计算到m1c即可即可 for(int j=0; j=jMax; j+) mnj=0; /0jwn, (4)式式 for(int j=wn; j1; i-) /i1表示对表示对i=1不处理，因为不处理，因为i=1时只需时只需求求m1c jMax=min(wi-1, c); for(int j=0; j=jMax; j+) /0jwi, (2)式式 mij=mi+1j; for(int j=w

43、i; j=w1) m1c=max(m2c, m2c-w1+v1); else m1c=m2c; 2021-12-14590-1背包问题: 算法（续） void Traceback(int w, int c, int n, int m, int x)/输出解输出解x1.n for(int i=0; in; i+) if(mic=mi+1c) xi=0; else xi=1; c -= wi; xn=(mnc)?1:0;n运行时间：运行时间：T(n)=O(cn) 2021-12-14600-1背包问题0 0 0 00 pi1(j wi) pi1(j)0 pi(j)0 目标目标 0i 1i n 0

44、j wi j M2021-12-1461111( )( )max( ),()iiiiiiiipjjwpjpjpjwpjw例：有例：有5个物体，其重量分别为个物体，其重量分别为2,2,6,5,4，价值，价值分别为分别为6,3,5,4,6，背包的载重量为，背包的载重量为10，求装入背，求装入背包的物体及其总价值包的物体及其总价值 2021-12-1462找零钱问题:问题描述n问题描述问题描述n一出纳员支付一定数量的现金。假设他一出纳员支付一定数量的现金。假设他手中有几种面值的硬币，要求他用最少手中有几种面值的硬币，要求他用最少的硬币数支付规定的现金。的硬币数支付规定的现金。例如，现有例如，现有3种

45、硬币：它们的面值分别为种硬币：它们的面值分别为1元、元、4元和元和6元。要支付元。要支付8元。元。2021-12-14630-1背包问题: 递归关系 不用第不用第i种硬币种硬币用第用第i种硬币种硬币11( )( )min( ),() 1iiiiiiipjjvp jpj p j vjv0(0)0( )ippj pi(j)：前：前i种硬币支付金额种硬币支付金额j所需硬币的最所需硬币的最少个数。少个数。 2021-12-14640 0 pi1(j)0 pi(j vi) pi(j)0 目标目标 0i 1i n 0 j vi j 811()()min( ),()1iiiiiiipjjvpjpjpjvjv

46、2021-12-14651元、元、4元和元和6元。要支付元。要支付8元。元。11( )( )min( ),() 1iiiiiiipjjvpjpjpjvjv012345678001012345678201231234230123121222021-12-1466某公司准备将新招聘的某公司准备将新招聘的4 4名销售员分配到下属名销售员分配到下属3 3个销售点个销售点甲、乙和丙。各销售点增加若干名销售员后可增加的甲、乙和丙。各销售点增加若干名销售员后可增加的月销售额如下表：月销售额如下表：增加销售额增加销售额（千元）（千元）增增1人人增增2人人增增3人人增增4人人甲甲12223038乙乙112024

47、30丙丙13253036根据此表，只要人员分配适当，公司每月最多根据此表，只要人员分配适当，公司每月最多可以增加销售额可以增加销售额（ ）千元。千元。动规练习2021-12-1467若给定序列若给定序列X=x1,x2,xm，则另一序列，则另一序列Z=z1,z2,zk，是，是X的子序列是指存在一个严格的子序列是指存在一个严格递增下标序列递增下标序列i1,i2,ik使得对于所有使得对于所有j=1,2,k有：有：zj=xij。例如，序列。例如，序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，相应的的子序列，相应的递增下标序列为递增下标序列为2，3，5，7。给定给定2个序列个

48、序列X和和Y，当另一序列，当另一序列Z既是既是X的子序列的子序列又是又是Y的子序列时，称的子序列时，称Z是序列是序列X和和Y的的公共子序公共子序列列。给定给定2个序列个序列X=x1,x2,xm和和Y=y1,y2,yn，找，找出出X和和Y的最长公共子序列。的最长公共子序列。 2021-12-1468设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长的最长公共子序列为公共子序列为Z=z1,z2,zk ，则，则(1)若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的的最长公共子序列。最长公共子序列。(2)若若xmyn且且zkxm，则，则Z是是xm-1和和Y的

49、最长公共的最长公共子序列。子序列。(3)若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共子的最长公共子序列。证明序列。证明: P57由此可见，由此可见，2个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2个序列的前缀个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。 2021-12-1469由最长公共子序列问题的最优子结构性质建立子问题最优值由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用的递归关系。用cij记录序列和的最长公共子序列的长度。记录序列和的最长公共子序列

50、的长度。其中，其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当。当i=0或或j=0时，空时，空序列是序列是Xi和和Yj的最长公共子序列。故此时的最长公共子序列。故此时Cij=0。其他情况。其他情况下，由最优子结构性质可建立递归关系如下：下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 1102021-12-1470Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m

51、; i+)5: for (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;15: 16: return cmn; 17:2021-12-14712021-12-1472最大子段和: 问题描述n给定整数序列给定整数序列a1,a2,an，求形如，求形如 的子段的子段和的最大值。规定子段和为负整数时，定义其和的最大值。规定子段和为负整数时，定义其最大子段和为最大子段和为0，即，即n例如，例如，(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) 最大子段和为最大子段和

52、为jikkajikknjiamaxmax1, 02042kka2021-12-1473最大子段和: 动态规划算法n基本思想基本思想 子问题定义子问题定义 考虑所有下标以考虑所有下标以j结束的最大子段和结束的最大子段和bj，即，即 原问题与子问题的关系原问题与子问题的关系 子问题解的递归关系子问题解的递归关系njamaxmaxjbjikkji,.,2 , 1, 01, 0, 01111jbmaxamaxmaxmaxamaxmaxnjjikkjinjjikknjinjajbjbj10, 1max2021-12-1474最大子段和: 动态规划算法（续）n算法算法int MaxSubSum3(int n, int a) int sum=0, b=0; /sum存储当前最大的存储当前最大的bj, b存储存储bj for(int j=1; j=n; j+) b += aj; if(bsum) sum=b; return sum; n运行时间：运行时间：T(n)=O(n)2021-12-1475发射导弹n某国为了防御敌