第六章动态规划

1、1第六章第六章 动态规划动态规划 6.1 动态规划的思想方法动态规划的思想方法 6.2 多段图的最短路径问题多段图的最短路径问题 6.3 资源分配问题资源分配问题 6.4 设备更新问题设备更新问题 6.5 最长公共子序列问题最长公共子序列问题 6.6 0/1 背包问题背包问题 6.7 RNA 最大碱基对匹配问题最大碱基对匹配问题26.1 动态规划的思想方法动态规划的思想方法 一一 动态规划的最优决策原理动态规划的最优决策原理 二二 动态规划实例、货郎担问题动态规划实例、货郎担问题 3一一 动态规划的最优决策原理动态规划的最优决策原理 1. 活动过程的分阶段决策活动过程的分阶段决策 2. 最优性

2、原理最优性原理 3. 最优决策的形成最优决策的形成 41. 活动过程的分阶段决策活动过程的分阶段决策把活动过程划分为若干个阶段，每一阶段的决策，依把活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下一阶段的决策依据发生转移，成为下一阶段的决策依据 P1 P2 Pn S0 S1 S2 Sn-1 Sn 52. 最优性原理最优性原理无论过程的初始状态和初始决策是什么，其余决策都必须无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决策序列相对于初始决策所产生的

3、状态，构成一个最优决策序列 S0 p(1,1) p(1,2) p(1,r1) s(1,1) s(1,2) s(1,r1) p(2,11) p(2,12) p(2,1r2) p(2,21) p(2,22) p(2,2r2) p(2,r11) p(2,r12) p(2,r1r2) s(2,11) s(2,12) s(2,1r2) s(2,21) s(2,22) s(2,2r2) s(2,r11) s(2,r12) s(2,r1r2) 63. 最优决策的形成最优决策的形成令最优状态为令最优状态为 s(2, 22)，由此倒推，由此倒推s(2, 22) p(2, 22) s(1, 2) p(1, 2)

4、s0 最优决策序列：最优决策序列： p(2, 22) p(1, 2) 状态转移序列：状态转移序列：s0 s(1, 2) s(2, 2) S0 p(1,1) p(1,2) p(1,r1) s(1,1) s(1,2) s(1,r1) p(2,11) p(2,12) p(2,1r2) p(2,21) p(2,22) p(2,2r2) p(2,r11) p(2,r12) p(2,r1r2) s(2,11) s(2,12) s(2,1r2) s(2,21) s(2,22) s(2,2r2) s(2,r11) s(2,r12) s(2,r1r2) 7最优决策的形成（续）最优决策的形成（续）1）最优决策在最

5、后阶段形成，然后向前倒推，直到初始）最优决策在最后阶段形成，然后向前倒推，直到初始 阶段阶段2）决策的具体结果及所产生的状态转移，由初始阶段开）决策的具体结果及所产生的状态转移，由初始阶段开 始进行计算，然后向后递归或迭代，直到最终结果始进行计算，然后向后递归或迭代，直到最终结果3）赖以决策的策略或目标，称为动态规划函数）赖以决策的策略或目标，称为动态规划函数4）动态规划函数可以递归地定义，也可以用递推公式）动态规划函数可以递归地定义，也可以用递推公式 表达表达5）整个决策过程，可以递归地进行，或用循环迭代的方）整个决策过程，可以递归地进行，或用循环迭代的方 法进行法进行8二二 动态规划实例、

6、货郎担问题动态规划实例、货郎担问题 1. 动态规划解货郎担问题的过程动态规划解货郎担问题的过程 2. 复杂性分析复杂性分析 91. 动态规划解货郎担问题的过程动态规划解货郎担问题的过程1）货郎担问题实例：）货郎担问题实例： 4城市的费用矩阵城市的费用矩阵2）动态规划函数：）动态规划函数： d(i, V)：从顶点：从顶点 i 出发，经出发，经 V 中各顶点一次，最中各顶点一次，最 终回到初始出发点的最短路径的长度终回到初始出发点的最短路径的长度 设初始出发点为设初始出发点为 i 573246325763=)c(=Cij)kV,k(d+cmin=) V, i (d=) i V, i (dikVk-

7、ikc=),k(dki103）工作过程）工作过程由城市由城市 1 出发，经城市出发，经城市 2, 3, 4然后返回然后返回1的最短路径长度为：的最短路径长度为： 573246325763=)c(=Cij, )4,3 ,2(d+cmin=)4,3 ,2 , 1(d12)3 ,2 ,4(d+c, )4,2 ,3(d+c1413)3 ,4(d+c,)4 ,3(d+cmin=)4,3 ,2(d2423)2 ,4(d+c,)4 ,2(d+cmin=)4,2 ,3(d3432)2 ,3(d+c,)3 ,2(d+cmin=)3,2 ,4(d43425=3+2=c+c=),4(d+c=)4 ,3(d41343

8、411=6+5=c+c=),3(d+c=)3 ,4(d3143436=3+3=c+c=),4(d+c=)4 ,2(d41242412=5+7=c+c=),2(d+c=)2 ,4(d2142428=6+2=c+c=),3(d+c=)3 ,2(d3123239=5+4=c+c=),2(d+c=)2 ,3(d213232112. 复杂性分析复杂性分析1）令）令 是从顶点是从顶点 i 出发，返回顶点出发，返回顶点 i 所需计算的形式为所需计算的形式为 d( k, Vk ) 的个数的个数2）开始计算）开始计算 d( i, Vi ) 时，集合时，集合 V i 中有中有 n 1 个顶点个顶点3）在计算）在计

9、算 d( k, V k ) 时，集合时，集合 V k 的顶点数目，的顶点数目， 在不同的决策阶段，分别为在不同的决策阶段，分别为 n - 2, , 04）在整个计算中，需要计算大小为）在整个计算中，需要计算大小为 j 的不同顶点集合的个的不同顶点集合的个 数为数为 ，j = 0, , n - 1。总个数为：。总个数为：5）当集合）当集合 V k 中的城市个数为中的城市个数为 j 时，为计算时，为计算 d( k, V k ) ，需，需 j 次加法，次加法，j - 1 次比较次比较 iNj1nC-1n0=jj1niC=N12复杂性分析（续）复杂性分析（续）6）从顶点）从顶点 i 出发，经其它城市再

10、回到出发，经其它城市再回到 i，总的运算时间为：，总的运算时间为： 由二项式定理：由二项式定理： 令令 x = y = 1, 得：得：7）动态规划方法求解货郎担问题，总花费）动态规划方法求解货郎担问题，总花费 T 为：为： -1n0=jj1n1n0=jj1n1n0=jj1niCn=CnC j=Tjnjn0=jjnnyxC=)y+x(-)2n(O=2nTn1ni-)2n(O=2nT=Tn21n2n1=ii-136.2 多段图的最短路径问题多段图的最短路径问题 一一 多段图的决策过程多段图的决策过程 二二 多段图动态规划算法的实现多段图动态规划算法的实现 14一一 多段图的决策过程多段图的决策过程

11、 1. 多段图的最短路径问题多段图的最短路径问题 2. 多段图最短路径的决策过程多段图最短路径的决策过程 3. 例子例子 4. 多段图最短路径问题实现步骤多段图最短路径问题实现步骤151. 多段图的最短路径问题多段图的最短路径问题1）多段图的定义：）多段图的定义： 有向连通赋权图有向连通赋权图 G = ，顶点集合，顶点集合 V 划分成划分成 k 个不相交的子集个不相交的子集 ，1 i k，k 2，使得，使得 E 中中 的任一边的任一边 (u, v)，必有，必有 u ，v ，m 1， 称称 G 为多段图。为多段图。 令令 ，称，称 为源点，为源点， 为收点为收点2）多段图的最短路径问题：）多段图

12、的最短路径问题： 求从源点到达收点的最小花费的通路求从源点到达收点的最小花费的通路 iViVm+iV1=|V|=|V|k11VskVt162. 多段图最短路径的决策过程多段图最短路径的决策过程1）顶点编号：）顶点编号： 根据多段图的根据多段图的 k 个不相交的子集个不相交的子集 ，把多段图划，把多段图划 分为分为 k 段，每一段包含顶点的一个子集段，每一段包含顶点的一个子集 顶点集合顶点集合 V 中的所有顶点，按照段的顺序编号中的所有顶点，按照段的顺序编号 子集中的顶点互不邻接，它们之间的相互顺序无子集中的顶点互不邻接，它们之间的相互顺序无 关紧要关紧要 顶点个数为顶点个数为 n，源点，源点

13、s 的编号为的编号为 0，收点，收点 t 的编的编 号为号为 n 1 对对 E 中的任何一条边中的任何一条边 (u, v)，顶点，顶点 u 的编号小于的编号小于 顶点顶点 v 的编号的编号 iV172）决策过程）决策过程 第一阶段，确定第第一阶段，确定第 k 1 段的所有顶点到达收点段的所有顶点到达收点 t 的花的花 费最小的通路，及通路上该顶点的前方顶点编号费最小的通路，及通路上该顶点的前方顶点编号 第二阶段，用第一阶段的信息，确定第第二阶段，用第一阶段的信息，确定第 k 2 段的所有段的所有 顶点到达收点顶点到达收点 t 的花费最小的通路，及通路上该顶点的的花费最小的通路，及通路上该顶点的

14、 前方顶点编号前方顶点编号 如此依次进行，直到最后确定源点如此依次进行，直到最后确定源点 s 到达收点到达收点 t 的花费的花费 最小的通路，及通路上该顶点的前方顶点编号最小的通路，及通路上该顶点的前方顶点编号 最后，从源点的信息的前方顶点编号，递推地确定整条最后，从源点的信息的前方顶点编号，递推地确定整条 路径上的所有顶点编号路径上的所有顶点编号183）动态规划函数）动态规划函数 工作单元描述：工作单元描述： cost i ：顶点：顶点 i 到达收点到达收点 t 的最小花费的最小花费 path i ：顶点：顶点 i 到达收点到达收点 t 的前方顶点编号的前方顶点编号 route n ：源点：

15、源点 i 到达收点到达收点 t 的最短通路上的顶点编号的最短通路上的顶点编号 动态规划函数：动态规划函数： (1) (2) j tcos+cmin= i tcosijnjinjij j tcos+c= i pathij最最小小的的使使193. 例子：求解图所示的最短路径问题例子：求解图所示的最短路径问题 i = 8： path 8 = 9i = 7： path 7 = 9 i = 6： path 6 = 8 9 1 4 5 4 8 6 6 7 7 7 8 0 2 5 9 1 6 1 8 6 8 3 3 4 3 6 5 7 3=0+3=9 tcos+c=8 tcos897=0+7=9 tcos+

16、c=7 tcos79 j tcos+cmin= i tcosijnjinjij j tcos+c= i pathij最最小小的的使使8=3+5,7+6min= 8 tcos+c, 7 tcos+cmin=6 tcos686720例子（续例子（续 1）i = 5： path 5 = 8i = 4： path 4 = 8i = 3： path 3 = 5 9 1 4 5 4 8 6 6 7 7 7 8 0 2 5 9 1 6 1 8 6 8 3 3 4 3 6 5 7 9=3+6,7+8min= 8 tcos+c, 7 tcos+cmin=5 tcos58579=3+6,7+5min= 8 tco

17、s+c, 7 tcos+cmin=4 tcos484713=8+7,9+4min= 6 tcos+c, 5 tcos+cmin=3 tcos363521例子（续例子（续 2）i = 2： path 2 = 3i = 1： path 1 = 5i = 0： path 0 = 2 9 1 4 5 4 8 6 6 7 7 7 8 0 2 5 9 1 6 1 8 6 8 3 3 4 3 6 5 7 14=6 tcos+c, 5 tcos+c, 4 tcos+c, 3 tcos+cmin=2 tcos2625242315=9+6,9+9min= 5 tcos+c, 4 tcos+cmin=1 tcos1

18、51415= 3 tcos+c, 2 tcos+c, 1 tcos+cmin=0 tcos03020122例子（续例子（续 3）path 0 = 2 path 1 = 5 path 2 = 3path 3 = 5 path 4 = 8 path 5 = 8path 6 = 8 path 7 = 9 path 8 = 9route 0 = 0 cost 0 = 15route 1 = path route 0 = path 0 = 2route 2 = path route 1 = path 0 = 3route 3 = path route 2 = path 3 = 5route 4 = pa

19、th route 3 = path 5 = 8route 5 = path route 4 = path 8 = 9 9 1 4 5 4 8 6 6 7 7 7 8 0 2 5 9 1 6 1 8 6 8 3 3 4 3 6 5 7 234. 多段图最短路径问题实现步骤多段图最短路径问题实现步骤 对所有的对所有的 i ，0 i 0，转，转 ；否则，转；否则，转 令令 i = 0，route 0 = 0 如果如果 riute i = n 1，算法结束；否则，转，算法结束；否则，转 i = i + 1，route i = path route i 1 ；转；转 24二二 多段图动态规划算法的实现多

20、段图动态规划算法的实现 1. 数据结构数据结构 2. 算法描述算法描述251. 数据结构数据结构struct NODE / 邻接表结点的数据结构邻接表结点的数据结构 int v_num;/ 邻接顶点的编号邻接顶点的编号 Type len;/ 邻接顶点与该顶点的费用邻接顶点与该顶点的费用 struct NODE *next;/ 下一个邻接顶点下一个邻接顶点 ;struct NODE noden;/ 多段图邻接表头结点多段图邻接表头结点Type costn;introuten;intpathn;262. 算法描述（步骤算法描述（步骤 ）4. Type fgraph(struct NODE node

21、 , int route , int n)5. int i;7. struct NODE *pnode;8. int *path = new int n ;9. Type min_cost, *cost = new Type n ;10. for (i=0; i=0; i-) O(n + m)15. pnode = node i -next;16. while (pnode != NULL) 17. if (pnode-len + costpnode-v_num len + costpnode-v_num;19. path i = pnode-v_num;20. 21. pnode = pno

22、de-next;22. 23. nextlenv_numnextlenv_numnext28算法描述（步骤算法描述（步骤 ）24. i = 0; O(k)25. while (route i != n-1) & (path i != -1) 26. i+;27. route i = path route i-1 ;28. 29. min_cost = cost 0 ;30. delete path; deleye cost;31. return min_cost; 32. 296.3 资源分配问题资源分配问题 一一 资源分配问题的决策过程资源分配问题的决策过程 二二 资源分配算法的实现资源分配

23、算法的实现 30一一 资源分配问题的决策过程资源分配问题的决策过程 1. 资源分配问题资源分配问题 2. 目标函数和约束方程目标函数和约束方程 3. 决策过程决策过程 4. 实现步骤实现步骤 5. 例子例子 311. 资源分配问题资源分配问题资源总数为资源总数为 r，工程个数为，工程个数为 n。给每项工程投入的资源。给每项工程投入的资源不同，所获得的利润也不同。要求把总数为不同，所获得的利润也不同。要求把总数为 r的资源的资源分配给分配给 n 个工程，以获得最大利润的分配方案个工程，以获得最大利润的分配方案 322. 目标函数和约束方程目标函数和约束方程把资源把资源 r 划分为划分为 m 个相

24、等的部分，个相等的部分，m 为整数为整数利润函数利润函数 ： x 份资源分配给第份资源分配给第 i 个工程所得到的利润个工程所得到的利润分配分配 m 份资源给所有工程，所得到的利润总额为：份资源给所有工程，所得到的利润总额为：使最大的分配方案：使最大的分配方案： mx0,ni1, )x(Gim=x)x(G=)m(Gn1=iiin1=ii)x,x,x(n21333. 决策过程决策过程1）定义两组变量）定义两组变量 ：把：把 x 份资源分配给前面份资源分配给前面 i 个工程所得到的最大利润个工程所得到的最大利润 ：使：使 最大时，分配给第最大时，分配给第 i 个工程的资源份额个工程的资源份额2）阶

25、段划分）阶段划分 n 个工程划分为个工程划分为 n 个阶段个阶段 第一阶段把第一阶段把 x ( x = 1, , m) 份资源分配给第一个工程份资源分配给第一个工程 第第 i 阶段把阶段把 x ( x = 1, , m) 份资源分配给前面份资源分配给前面 i 个工程个工程 i = 2, , n)x(fi)x(di)x(fi343）分配份额为）分配份额为 x ( x = 1, , m ) 时，第时，第 i 阶段的最大利润阶段的最大利润 及第及第 i 工程的最优分配份额工程的最优分配份额 ( i = 1, , n )第一阶段，只把第一阶段，只把 x 份资源分配给第一个工程份资源分配给第一个工程 f

26、1(x) = G1(x) 0 x m d1(x) = x在第二阶段，把在第二阶段，把 x 份资源分配给前面两个工程份资源分配给前面两个工程 f2(x) = max G2(z) + f1(x z) 0 x m, 0 z x d2(x) = 使使 f2(x) 达最大的达最大的 z在第在第 i 阶段，把阶段，把 x 份资源分配给前面份资源分配给前面 i 个工程个工程 fi(x) = max Gi(z) + fi-1(x z) 0 x m, 0 z x d2(x) = 使使 fi(x) 达最大的达最大的 z354）分配份额为）分配份额为 m 时，第时，第 i 阶段的最大利润阶段的最大利润 gi 及前面

27、及前面 i 个工程个工程 的最优分配份额的最优分配份额 qi ( i = 1, , n )5）全局最大利润）全局最大利润 optg 及所分配工程项目的最大数目及所分配工程项目的最大数目 k 6）全局最大利润下）全局最大利润下 k 个工程的最优份额个工程的最优份额 optx7）全局最大利润下分配给第）全局最大利润下分配给第 i 个工程的最优份额个工程的最优份额 )m(f , )1(fmax=giiix)x(f=qii达达最最大大的的使使g,gmax=optgn1ig=ki最大的最大的使使iiqg=optx相相对对应应的的与与最最大大的的)optx(d=optqkkkoptq368）分配给其余个工

28、程的剩余的最优份额分配给其余个工程的剩余的最优份额 9）回溯，得到分配给前面各个工程的最优份额的递推关系式）回溯，得到分配给前面各个工程的最优份额的递推关系式 i = k 1, , 1)optx(doptx=optxk-iiioptq-optx=optx)optx(d=optq374. 实现步骤实现步骤1）对各个阶段，各个不同份额的资源，计算）对各个阶段，各个不同份额的资源，计算 及及2）计算各个阶段的最大利润）计算各个阶段的最大利润 ，及获得此最大利润的分，及获得此最大利润的分 配份额配份额3）计算全局的最大利润）计算全局的最大利润 optg，总的最优分配份额，总的最优分配份额 optq 及

29、最大的工程项目说数目及最大的工程项目说数目 k4）递推计算各个工程的最优分配份额）递推计算各个工程的最优分配份额)x(fi)x(diigiq385. 例子例子8 个份额的资源，分配给个份额的资源，分配给 3 个工程，其利润函数如下个工程，其利润函数如下第一阶段，直接给出第一阶段，直接给出 X012345678G10426404550515253G20515406070737475G306154080909598100X012345678F10426404550515253D101234567839例子例子第二阶段第二阶段 X012345678G20515406070737475G3061540

30、80909598100X012345678f10426404550515253d1012345678X=10,11,0f2d2f24551X=20,21,12,0f226915260X=30,31,22,13,0f240312040400X=40,41,32,23,14,0f2454541446060440例子例子第二阶段第二阶段 X012345678G20515406070737475G306154080909598100X012345678f10426404550515253d1012345678X=50,51,42,33,24,15,0f2d2f2505055666470705X=60,

31、61,52,43,34,25,16,0f251556080867473864X=70,71,62,53,44,35,26,17,0f2525665851009677741004X=80,81,72,63,54,45,36,27,18,0f253576690105110997875110541例子例子第第optg = max(53, 110, 140) = 140 q3 = 8 k = 3 optx = 8X012345678gf1042640455051525353d1012345678f2052640607086100110110d2010045445f3052640809010612014

32、0140d30100454444=4-8=optq-optx=optx4=)8(d=optq3330=4-4=optq-optx=optx4=)4(d=optq3220=)0(d=optq1142二二 资源分配算法的实现资源分配算法的实现 1. 数据结构数据结构 2. 算法描述算法描述 431. 数据结构数据结构intm;/ 可分配的资源份额可分配的资源份额 intn;/ 工程项目个数工程项目个数 Type Gnm+1;/ 工程的利润表工程的利润表 Type optg;/ 最优的总利润最优的总利润intoptqn;/ 工程最优分配份额工程最优分配份额Type fnm+1;/ 各阶段不同资源份额

33、的最大利润各阶段不同资源份额的最大利润intdnm+1;/ fix 最大时最大时,第第i项工程的分配份额项工程的分配份额Type gn;/ 阶段的最大利润阶段的最大利润 intqn;/ 第第 i 阶段第阶段第 i 工程最优分配份额工程最优分配份额intoptx;/ 最优分配时的资源最优分配份额最优分配时的资源最优分配份额 intk;/ 最优分配时的工程项目数最优分配时的工程项目数442. 算法描述（步骤算法描述（步骤 ） 2. Type allot_res(int n, int m, Type G , int optq ) 3. 4. int optx, k, i, j, x; 5. int

34、*q = new int n ; / 分配工分配工作单元作单元 6. int (*d)m+1 = new int n m+1 ; 7. Type (*f)m+1 = new Type n m+1 ; 8. Type *g = new Type n ; 9. for (j=0; j=m; j+) / 第一个工程的份额利润表第一个工程的份额利润表10. f 0 j = G 0 j ; d 0 j = j;11. 45算法描述（步骤算法描述（步骤 ）12. for (i=1; in; i+) 13. f i 0 = G i 0 + f i-1 0 ; d i 0 = 0;15. for (j=1;

35、j = m; j+) 16. f i j = f i 0 ; d i j = 0;17. for (x=0; x = j; x+) 18. if (f i j G i x +f i-1 j-x ) 19. f i j = G i x + f i-1 j-x ;20. d i j = x; 21. 22. 23. 24. 46算法描述（步骤算法描述（步骤 ）25. for (i=0; in; i+) 24. g i = f i 0 ; q i = 0;25. for (j=1; j = m; j+) 26. if (g i f i j ) 27. g i = f i j ; q i = j; 3

36、0. 31. optg = g 0 ; optx = q 0 ; k = 0;32. for (i=1; i n; i+) 33. if (optg g i ) 34. optg = g i ; optx = q i ; k = i; 36. 47算法描述（步骤算法描述（步骤 ）37. if (k n-1) / 最大编号之后的最大编号之后的38. for (i=k+1; i= 0; i-) / 最大编号之前的最大编号之前的41. optq i = d i optx ;/工程分配份额工程分配份额42. optx = optx optq i ;43. 44. delete q; delete d;

37、 45. delete f; delete g; 46. return optg;47. 486.4 设备更新问题设备更新问题 一一 设备更新问题的决策过程设备更新问题的决策过程 二二 设备更新算法的实现设备更新算法的实现 49一一 设备更新问题的决策过程设备更新问题的决策过程1. 设备更新问题：设备更新问题： 设备的性能随使用年限的增加而变坏，导致收入减少设备的性能随使用年限的增加而变坏，导致收入减少 维修费增加，利润下降。而设备的更新，需付出一笔维修费增加，利润下降。而设备的更新，需付出一笔 经费，但可增加利润收入。设备的更新问题是确定设经费，但可增加利润收入。设备的更新问题是确定设 备的

38、最优更新策略，使得在一个确定期限里，为公司备的最优更新策略，使得在一个确定期限里，为公司 创造最大的利润。创造最大的利润。50一一 设备更新问题的决策过程设备更新问题的决策过程2. 设备更新的有关数据：设备更新的有关数据：I = 0一列，表明现有设备的有关数据；一列，表明现有设备的有关数据；I = 1一列，表示第一年购买的设备的有关数据；其余类推。一列，表示第一年购买的设备的有关数据；其余类推。使用年限中的第使用年限中的第0列，表示当年的有关数据，列，表示当年的有关数据，第第1列表示使用一年后的有关数据，其余类推；列表示使用一年后的有关数据，其余类推；利润、维修费用、更新费用等行分别表示：在第

39、利润、维修费用、更新费用等行分别表示：在第 i 年购买的设年购买的设备使用了备使用了 j 年后，可以创造的利润、必须付出的维修费用以及年后，可以创造的利润、必须付出的维修费用以及进行更新时需要付出的费用进行更新时需要付出的费用。 购买时间购买时间I=0I=1I=2I=3I=45使用年限使用年限2 3 4 5 6 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0利利 润润13 12 11 10 916 15 14 13 1217 16 15 1418 17 1619 1820维修费用维修费用 2 3 4 4 5 1 1 2 2 3 1 1 2 2 1 1 2 1 1 1更新费用更新费用

40、25 26 27 28 29 20 22 24 25 2620 22 24 2520 22 2421 22 2151一一 设备更新问题的决策过程设备更新问题的决策过程52一一 设备更新问题的决策过程设备更新问题的决策过程53一一 设备更新问题的决策过程设备更新问题的决策过程4. 利润函数：利润函数： 1）使用了）使用了 t 年的设备，第年的设备，第 i 年决定更新，利润函数如下年决定更新，利润函数如下 (6.4.1) 2）第年决定保留继续使用，则有利润函数如下）第年决定保留继续使用，则有利润函数如下 (6.4.2) itftumritftumrtbuyiiiitiiii)1()()0()0()

41、1()()0()0()(101ittftmtrittftmtrtremiititii)1()()()1()()()(100154一一 设备更新问题的决策过程设备更新问题的决策过程5. 规划函数：规划函数： 1） (6.4.1) 2） (6.4.2) )(),(max)(tremtbuytfiii)()()()()(tremtbuyFALSEtremtbuyTRUEtxiiiii55一一 设备更新问题的决策过程设备更新问题的决策过程 56一一 设备更新问题的决策过程设备更新问题的决策过程 57一一 设备更新问题的决策过程设备更新问题的决策过程 58二二 设备更新算法的实现设备更新算法的实现1.

42、数据结构：数据结构： int n;/* 决策年限决策年限 */ int D;/* 设备当前的使用年限设备当前的使用年限 */ Type rnn+D; /*使用使用t年后的设备年后的设备,在第在第 i 年所创造的利润年所创造的利润*/ Type mnn+D; /* 使用使用 t 年后的设备年后的设备,在第在第 i 年的维修费用年的维修费用 */ Type unn+D; /* 使用使用 t年后的设备年后的设备,在第在第 i 年的更新费用年的更新费用*/ Type fnn;/* 使用使用 t 年后的设备年后的设备,在第在第 i 年及其以后所创年及其以后所创 造的利润造的利润 */ BOOL xnn;

43、/* 使用使用 t 年后的设备年后的设备,在第在第 i 年的更新决策年的更新决策 */ BOOL pn;/* 每年的最优决策每年的最优决策 */ 59二二 设备更新算法的实现设备更新算法的实现2. 算法描述：算法描述： 2. Type update_dev(int n,int D,Type r ,Type m , Type u ,BOOL p ) 3. 4. int i,j,k;/* 分配工作空间分配工作空间 */ 5. Type optg,rem; 6. Type (*f)n+1 = new Typen+2n+1; 7. BOOL (*x)n+1 = new BOOLn+1n+1; 8. f

44、or (i=1;i0;i-) /*第第1年年第第n年各种设备使用年限的利润年各种设备使用年限的利润*/11. for (j=1;jj) /* 买买,可得到的利润可得到的利润 */ 13. fij = ri0 mi0 ui-jj + fi+11;14. else15. fij = ri0 mi0 u0j-1+D + fi+11; 16. xij = TRUE;17. if (ij) /* 留留,可得到的利润可得到的利润 */18. rem = ri-jj mi-jj + fi+1j+1;19. else20. rem = r0j-1+D m0j-1+D +fi+1j+1;21. if (fijr

45、em) /* 决策决策,取二者中只最大者取二者中只最大者 */22. fij = rem; xij = FALSE;23. 24. 25. 61二二 设备更新算法的实现设备更新算法的实现26. j = 1;/* 全局的更新决策全局的更新决策 */27. for (i=1;i=n;i+) 28. pi = xij;/* 从第一年的决策开始从第一年的决策开始 */29. if (pi) /* 当年的决策：更新当年的决策：更新 */30. j = 1/* 下一年决策时下一年决策时,设备年限为设备年限为1年年 */31. else 32. j = j + 1;/*否则否则,下一年决策时下一年决策时,设

46、备年限增设备年限增1 */33. 34. optg = f11;35. delete f; delete x; /* 释放工作空间释放工作空间 */36. return optg;/* 返回最优更新时可得到的利润返回最优更新时可得到的利润 */37. 626.5 最长公共子序列问题最长公共子序列问题 一一 最长公共子序列的搜索过程最长公共子序列的搜索过程 二二 最长公共子序列算法的实现最长公共子序列算法的实现 63一一 最长公共子序列的搜索过程最长公共子序列的搜索过程 1. 最长公共子序列问题最长公共子序列问题 2. 最长公共子序列的性质最长公共子序列的性质 3. 最长公共子序列的搜索过程最长

47、公共子序列的搜索过程641. 最长公共子序列问题最长公共子序列问题1）字符子序列：）字符子序列： 上的字符序列上的字符序列 ，及，及 , 若对所若对所 有的有的 k, k = 1, 2, , j，有，有 ，其中，其中，1 ik n，是，是 A 的下标递增序列，称的下标递增序列，称 S 是是 A 的子序列。的子序列。例：例： = x, y, z ，A = x y z y x z x z x x x 是长度为是长度为 3 的子序列的子序列 x z y z x 是长度为是长度为 5 的子序列的子序列例：例：A = x y z y x z x z，B = x z y x x y z x x x x 是

48、长度为是长度为 3 的公共子序列的公共子序列 x z y z 是长度为是长度为 4 的公共子序列的公共子序列 x z y x x z是长度为是长度为 6 的最长公共子序列的最长公共子序列 n21aaa=Aj21ccc=Sikka=c652）最长公共子序列问题）最长公共子序列问题给定序列给定序列 和和 ，寻找，寻找 A 和和 B 的一个公共子序列，使得它是的一个公共子序列，使得它是 A 和和 B 的最长公的最长公共子序列共子序列 n21aaa=Am21bbb=B662. 最长公共子序列的性质最长公共子序列的性质令令 ， 记记 为序列为序列 A 中最前面连续中最前面连续 k 个字符的子序列个字符的

49、子序列记记 为序列为序列 B 中最前面连续中最前面连续 k 个字符的子序列个字符的子序列1）若）若 ， 是是 A 和和 B 的长度为的长度为 k 的最长的最长 公共子序列。则序列公共子序列。则序列 是是 A 和和 B 的长度为的长度为 k 1 的最长公共子序列的最长公共子序列2）若）若 , ，则，则 是是 和和 B 的的 长度为长度为 k 的最长公共子序列的最长公共子序列3）若）若 , ，则，则 是是 A 和和 的的 长度为长度为 k 的最长公共子序列的最长公共子序列 n21aaa=Am21bbb=Bk21kaaa=Ak21kbbb=Bmnb=ak21kccc=S1k211kccc=S-mnb

50、a knca k21kccc=S-1nAmnba kmcbk21kccc=S-1nB673. 最长公共子序列的搜索过程最长公共子序列的搜索过程1）最长公共子序列长度的递推关系式：）最长公共子序列长度的递推关系式： 记记 为为 和和 的最长公共子序列长度，则的最长公共子序列长度，则j , iLiAjBmj1,ni10=L=L=Lj ,00, i0,0jij-1,i-1j , iji-1j-1,ij , ibaL,Lmaxb=a1+L=Laiai-1bjbj-1682）阶段的划分和最长公共子序列长度的获取）阶段的划分和最长公共子序列长度的获取第一阶段：计算第一阶段：计算 和和 的最长公共子序列的长

51、度的最长公共子序列的长度第二阶段：计算第二阶段：计算 和和 的最长公共子序列的长度的最长公共子序列的长度第第 n 阶段：计算阶段：计算 和和 的最长公共子序列的长度的最长公共子序列的长度第第 n 阶段的阶段的 便是序列便是序列 和和 的最长公共子序列的的最长公共子序列的长度长度 1AjBm,2 , 1=j,Lj , 12AjBm,2 , 1=j,Lj ,2nAjBm,2 , 1=j,Lj ,nm,nLnAmB693）最长公共子序列的获取）最长公共子序列的获取 设置二维状态字数组设置二维状态字数组 ：j , is1=sj , i2=sj , i3=sj , ijib=ajiba 1j , ij

52、, 1iLL-jiba 1j , ij , 1iLL-70 最长公共子序列的搜索最长公共子序列的搜索设设 ， 是是 和和 的长度为的长度为 k 的最长公的最长公共子序列。搜索过程如下：共子序列。搜索过程如下： ： 下一个搜索方向是下一个搜索方向是 ： 下一个搜索方向是下一个搜索方向是 ： 下一个搜索方向是下一个搜索方向是递推关系：递推关系： 若若 则：则： ，i = i 1, j = j 1, k = k 1 若若 则：则： i = i 1 若若 则：则：j = j 11m, 1ns-1=sm,nmnb=anka=c2=sm,n3=sm,njiba 1j , ij , 1iLL-m, 1ns-

53、jiba 1j , ij , 1iLL-1m,ns-k=Lm,nk21kccc=SnAmB1=sj , i2=sj , i3=sj , iika=c714. 例例 1xzyzxyzxyzxy012345678910111200000000000000X10111313131113131113131113Y20121221232321232321232321X30111222223133333133333133Z40122122313232414343414343Y50122231323241424251535351X60112232324142425152526163Y701222313242

54、51535261636271Z80122132414252616362717372Z90122132414252616262717272y1001222314242516262717272jij-1,i-1j , iji-1j-1,ij , ibaL,Lmaxb=a1+L=L=sj , ijib=a11j , ij , 1iLL2-1j , ij , 1iLL3-724. 例例 1xzyzxyzxyzxy012345678910111200000000000000X10111313131113131113131113Y20121221232321232321232321X30111222223

55、133333133333133Z40122122313232414343414343Y50122231323241424251535351X60112232324142425152526163Y70122231324251535261636271Z80122132414252616362717372Z90122132414252616262717272y10012223142425162627172721=sj , i2=sj , i3=sj , i1-k=k,1- j=j,1- i=i,a=cik1- i=i1- j=j73二二 最长公共子序列算法的实现最长公共子序列算法的实现1. 数据结构

56、数据结构 2. 算法描述算法描述 741. 数据结构数据结构下面的数据用于算法的输入和输出：下面的数据用于算法的输入和输出：charAn+1,Bm+1;/ 序列序列 A 和和 B char Cn+1;/ 序列序列 A 和和 B 的公共子序列的公共子序列 下面的数据用于算法的工作单元：下面的数据用于算法的工作单元：int Ln+1m+1;/ 搜索过程中的子序列长度搜索过程中的子序列长度 int sn+1m+1;/ 搜索过程中的子序列状态搜索过程中的子序列状态 752. 算法描述（初始化部分）算法描述（初始化部分）1. int lcs(char A , char B , char C , int

57、n, int m) 2. 3. int i, j, k, len;/ 分配工作空间分配工作空间 4. int (*L)m+1 = new int n+1m+1; 5. int (*s)m+1 = new intn+1m+1; 6. for (i=0;i=n;i+)/ 初始化第初始化第0列列 7. L i 0 = 0; 8. for (i=0;i=m;i+)/ 初始化第初始化第0行行 9. L 0 i = 0;76算法描述（计算长度及状态字）算法描述（计算长度及状态字）10. for (i=1;i=n;i+) 11. for (j=1;j= L i j-1 ) 17. L i j = L i-1

58、 j ; s i j = 2; 20. else 21. L i j = L i j-1 ; s i j = 3; 24. 25. 77算法描述（搜索最长公共子序列字符算法描述（搜索最长公共子序列字符 ）26. i = n; j = m; k = len = L i j ;27. while ( i!=0 )&( j!=0 ) 28. switch (s i j ) 29. case 1: C k = A i ; k-; j-; 31. case 2: i-; break;32. case 3: j-; break; 33. 34. 35. delete L; delete s;/ 释放工作空

59、间释放工作空间36. return len;/ 返回最长公共子序列长度返回最长公共子序列长度37. 6.6 0/1 背包问题背包问题一一 0/1背包问题的求解过程背包问题的求解过程二二 0/1背包问题的实现背包问题的实现 一一 0/1背包问题的求解过程背包问题的求解过程一一 0/1背包问题的求解过程背包问题的求解过程一一 0/1背包问题的求解过程背包问题的求解过程一一 0/1背包问题的求解过程背包问题的求解过程一一 0/1背包问题的求解过程背包问题的求解过程一一 0/1背包问题的求解过程背包问题的求解过程二二 0/1背包问题的实现背包问题的实现1. 数据结构和变量：数据结构和变量： int w

60、n;/* n个物体的重量个物体的重量 */ Type pn;/* n个物体的价值个物体的价值 */ int m;/* 背包的载重量背包的载重量 */ BOOL xn;/* 装入背包的物体装入背包的物体,元素为元素为TRUE */ /* 时时,对应物体被装入对应物体被装入 */ Type v;/* 装入背包中物体的最大价值装入背包中物体的最大价值 */ Type optpn+1m+1; /* i个物体装入载重量为个物体装入载重量为 j的的 */ /* 背包中的最大价值背包中的最大价值 */二二 0/1背包问题的实现背包问题的实现2. 算法描述：算法描述： 1. template 2. Type