第8章 动态规划

1、2作者：（美）作者：（美）Anany Levitin 译者：潘彦译者：潘彦出版社：清华大学出版社：清华大学丛书名：国外经典教材丛书名：国外经典教材 计算机计算机 科学与技术科学与技术4w动态规划动态规划（Dynamic Programming），在），在20 世世纪纪50年代由美国数学家年代由美国数学家Richard Bellman（理查（理查德德 .贝尔曼）发明，作为贝尔曼）发明，作为的的一种通用方法，对最优化问题提出一种通用方法，对最优化问题提出，从，从而创建最优化问题的一种新算法设计技术而创建最优化问题的一种新算法设计技术动态动态规划规划，它是一种重要的应用数学工具。至少在计算，它是一种

2、重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种化问题，而最终把它作为一种通用的通用的算法设计技术，算法设计技术，即包括某些非最优化问题。即包括某些非最优化问题。5w多阶段决策过程最优化多阶段决策过程最优化： 现实世界里有许多问题属于这种情况：它有很现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的

3、组合问很高、计算量很大的问题（如求最佳子集的组合问题），要找出一切可能解，所耗费的计算时间可能题），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了降低求解问题的是不可以接受的。因此，人们为了降低求解问题的难度，把求解过程分为难度，把求解过程分为一系列阶段一系列阶段，各个阶段依次，各个阶段依次按照最优性原则计算，最后阶段计算得到按照最优性原则计算，最后阶段计算得到最优解最优解。包括包括 分段分段、求解求解 两大步。两大步。6求解算法求解算法求解算法求解算法求解算法求解算法：求解算法施加的状态：求解算法施加的状态是变化的。当前状态只与其直接前是变化的。当前状态只与其直接前趋状

4、态有关，对其直接前趋状态施趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。加求解算法，成为当前状态。(Principle of Optimality)：子实例组成父实例，父实例分子实例组成父实例，父实例分解为子实例。解为子实例。7 对于某些多阶段决策问题，问题本身没有最优化要对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的计算裴波那契序列以及计算二项求，比如后面要讲到的计算裴波那契序列以及计算二项式系数的动态规划算法，它们式系数的动态规划算法，它们属于非最优化问题属于非最优化问题的动态的动态规划法。规划法。：1. 分阶段（级）决策。对最优化问题，用最优性原则设分阶段（级

5、）决策。对最优化问题，用最优性原则设计。计。2. 一般采用一般采用（规模减小），（规模减小），（规模增加）。计算过程是一级一级（一阶段一阶段）（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。地向前推进，直到最终状态。8910v解决问题的基本特征解决问题的基本特征 1. 动态规划一般解决最值（最优，最大，最小，最动态规划一般解决最值（最优，最大，最小，最长长）问题；）问题； 2. 动态规划解决的问题一般是离散的，可以分解动态规划解决的问题一般是离散的，可以分解（划分阶段）的；（划分阶段）的； 3. 动态规划解决的问题必须包含最优子结构，即可动态规划解决的问题必须包含最优

6、子结构，即可以由（以由（n1）的最优推导出）的最优推导出n的最优；的最优；11v解决问题的基本步骤解决问题的基本步骤w设计一个标准的动态规划算法的步骤：设计一个标准的动态规划算法的步骤：w实际应用当中的简化步骤：实际应用当中的简化步骤：12 步骤步骤1：用：用F（n）表示在斐波纳契数列中第）表示在斐波纳契数列中第n个数的值；个数的值； 步骤步骤2：状态转移方程：状态转移方程： 步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解 步骤步骤4：在数组中分析构造出问题的解：在数组中分析构造出问题的解F(n) = nif n = 0 or 1F(n-1) + F(n-2)if n

7、113递归版本递归版本:F(n)1if n=0 or n=1 then2return n3else4return F(n-1) + F(n-2)动态规划动态规划:F(n)1A0 0,A1 12for i 2 to n do3Ai Ai-1 + Ai-24return An太慢太慢!有效率!算法复杂度是 O(n)1415 步骤步骤1：用：用表示二项式系数；表示二项式系数； 步骤步骤2：状态转移方程：状态转移方程： 步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解 步骤步骤4：在数组中分析构造出问题的解：在数组中分析构造出问题的解C(n,k) = 1if k = 0 or n

8、 if n k016171819问题问题：设有一三角形数塔如图。求一条自塔顶到塔底的路，设有一三角形数塔如图。求一条自塔顶到塔底的路，该路径上节点值之和最大该路径上节点值之和最大。分段：分段：每一级台阶为一个阶段，成为多阶段决策的优化问题。每一级台阶为一个阶段，成为多阶段决策的优化问题。求解：求解：动态规划法求解。自底向上计算，各实例计算满足最动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例优性原则，如实例1818的子实例为的子实例为1212和和7 7，max(12+6, 7+6)=18max(12+6, 7+6)=18。5 级级4 级级3 级级2 级级1级级18 27 39 3

9、267 46 6578 73911311874014261582467131211205950 4938 34 2921 28 19 2119 7 10 4 1621数组数组data912 1510 6 8 2 18 9 519 7 10 4 16数组数组d5950 4938 34 2921 28 19 2119 7 10 4 1622w输入规模输入规模：为便于分析，选择数塔层数为便于分析，选择数塔层数k (k0)；w基本操作基本操作：节点值求和运算；节点值求和运算；增长函数增长函数：加法次数：加法次数与与 k 的关系；的关系；w效率类别效率类别：没有最佳、最差情况；（都要从塔顶计没有最佳、最

10、差情况；（都要从塔顶计算到塔底）算到塔底）w增长率（次数）增长率（次数）： 各层节点数升序：各层节点数升序：1, 2, 3, 4, , 6, 7, 8, 9, 10, . 节点总数节点总数 n 升序：升序：1, 3, 6, 10, , 21, 28, 36, 45, 55, . 层数层数k（顶为（顶为1）：）：1, 2, 3, 4, , 6, 7, 8, 9, 10, . 路径总数路径总数 t 升序：升序： 2, 4, 8, , 32, ., t = , k1231. 穷举法穷举法：T(k) = (k-1) 2k-1，k1 （） 本例本例k=5，每条路径上，每条路径上5个节点做个节点做4次加法

11、，共次加法，共64次次加法。加法。2. 动态规划法动态规划法：（层节点数层节点数 = 层数层数） 自底向上计算，自底向上计算，k层加法总数为层加法总数为k-1层节点数层节点数2，有效率计算式：有效率计算式： T(k) = 2(k-1+.+3+2+1) = k(k-1), k1 （） 本例加法总数本例加法总数 2(4+3+2+1) = 20次，比次，比64次少很次少很多。多。24（区别于完全最短路径问题）（区别于完全最短路径问题）概念概念：给定一个有向无环图（：给定一个有向无环图（DAG图），求给定起始顶点图），求给定起始顶点到结束顶点的最短路径，此即单起点（单源）最短路径到结束顶点的最短路径，

12、此即单起点（单源）最短路径问题。问题。 DAG的独特之处是所有节点可以线性化（拓扑序列），的独特之处是所有节点可以线性化（拓扑序列），使得所有边保持由左到右的方向（如下图）。使得所有边保持由左到右的方向（如下图）。423109 67103848965484源点源点收点收点2526分段分段1：27分段分段2：图示求解过程：红色数字为实例求解结果（最优性原则）图示求解过程：红色数字为实例求解结果（最优性原则）4本例：带权有向图本例：带权有向图23109 67103848965484源点源点收点收点28010000010000101234123410A 11111100011123412341110

13、1T 邻接矩阵邻接矩阵 一个一个n个顶点有向图的个顶点有向图的为一个为一个n阶布尔矩阵阶布尔矩阵T= ti j ：如果从：如果从i 到到 j 顶点间存在一条有向路径，那么矩阵第顶点间存在一条有向路径，那么矩阵第 i 行第行第 j 列置列置1 即即Ti, j=1；否则置否则置0即即Ti, j=0。例如，因有。例如，因有2412有向路径故有向路径故t22=1。传递闭包给出。传递闭包给出给定图各顶点之间是否存在任意长度的有向路径。（给定图各顶点之间是否存在任意长度的有向路径。（）v （T初始化为初始化为0矩阵）矩阵）任意顶点任意顶点 k 出发，将本轮出发，将本轮DFS或或BFS遍历能访问到的顶点置遍

14、历能访问到的顶点置1（k 行）。行）。本轮遍历结束，可能存在没访问到的顶点本轮遍历结束，可能存在没访问到的顶点（非连通图、无有向路径）。（非连通图、无有向路径）。从每个顶点出发遍历，即可生成图的传递闭包。由于这个方法对同一个从每个顶点出发遍历，即可生成图的传递闭包。由于这个方法对同一个有向图遍历了多次（有向图遍历了多次（n次），时间效率不高，希望找到更好的算法。次），时间效率不高，希望找到更好的算法。包含起始顶点和终止顶点都是包含起始顶点和终止顶点都是同一个顶点的回路（若存在）同一个顶点的回路（若存在）29w 动态规划法策略动态规划法策略：将问题分段如图，然后：将问题分段如图，然后 一级一级向

15、前推进计算。本例一级一级向前推进计算。本例 Warshall 算法通过计算一系列算法通过计算一系列 n 阶矩阵阶矩阵R(k)来构造来构造 最终阶段最终阶段 n 阶传递闭包矩阵阶传递闭包矩阵R(n)： , R(1) , . , R(k), . , R(n-1) , 中间矩阵中间矩阵 R(0) 该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的 任意顶点出发的路径不含有中间顶点，此即任意顶点出发的路径不含有中间顶点，此即。 R(1) 允许路径中包含第允许路径中包含第1个顶点（本例编号个顶点（本例编号 1）作为中间顶点。）作为中间顶点。 R(2)

16、 允许路径中包含前允许路径中包含前2个顶点（本例编号个顶点（本例编号1 2）作为中间顶点。）作为中间顶点。 R(k) 允许路径中包含前允许路径中包含前k个顶点作为中间顶点。个顶点作为中间顶点。 R(n) 允许路径中包含全部允许路径中包含全部 n 个顶点作为中间顶点。个顶点作为中间顶点。 每个后继矩阵每个后继矩阵 R(k) 对其前趋对其前趋 R(k-1) 来说，在路径上允许增加一个顶点，来说，在路径上允许增加一个顶点， 因此有可能包含更多的因此有可能包含更多的1（）。）。41111111100001111123412323414nTk 级级30(0)00000010000111012341203

17、4R 路径中不允许包含中间顶点，路径中不允许包含中间顶点，即邻接矩阵。框起来的行和列即邻接矩阵。框起来的行和列用于计算后继矩阵用于计算后继矩阵 ：本例本例R(1)4, 2=1。(1)01000010000110142301R 路径中允许包含第一个顶点作为中间顶点，即路径中允许包含第一个顶点作为中间顶点，即允许包含编号不大于允许包含编号不大于1的中间顶点（即的中间顶点（即1）。）。新增新增1条路径：条路径：4 2 (原有原有2条路径条路径 42)框起来的行和列用于计算后继矩阵框起来的行和列用于计算后继矩阵 。(2)01000010000111112413R 路径中允许包含前路径中允许包含前2个顶

18、点作为中间顶点，即个顶点作为中间顶点，即允许包含编号不大于允许包含编号不大于2的中间顶点（即的中间顶点（即1 2）。）。新增新增2条路径：条路径：1 4 , 44框起来的行和列用于计算后继矩阵框起来的行和列用于计算后继矩阵 。31(3)100001000012311123404111R 路径中允许包含前路径中允许包含前3个顶点作为中间顶点，即个顶点作为中间顶点，即允许包含编号不大于允许包含编号不大于3的中间顶点（的中间顶点（123）。）。没有新增路径。框内元素计算矩阵没有新增路径。框内元素计算矩阵 。(4)11100001111111121134R 路径中允许包含前路径中允许包含前4个顶点作为

19、中间顶点，即个顶点作为中间顶点，即允许包含编号不大于允许包含编号不大于4的中间顶点（的中间顶点（1234）。）。新增新增5条路径，红色数字表示。例如条路径，红色数字表示。例如R(4)1, 1前趋前趋R(3)中存在中存在1 、 1两条路径，合成两条路径，合成1 1。(0)( )(1)(1)( )(1);()/k/(1)(1) , , ( , , );1. ,1. )/;1kkkkn nknfortodofortodofortodoorWarshell AnandreturnRAinjnRi jRi jRi knknRjARkR 输输入入邻邻接接矩矩阵阵级级 循循环环行行循循环环列列循循环环返返回

20、回传传递递闭闭包包。矩矩阵阵带带上上标标便便于于理理解解。运算运算运算运算同同1为为1， 同同0为为0行列看作比特串行列看作比特串32给定一个给定一个带权连通图带权连通图（有向或无向），要求找出从每个顶点到其他所有（有向或无向），要求找出从每个顶点到其他所有顶点之间的顶点之间的距离距离（最短路径的长度），这就是完全最短路径问题。（最短路径的长度），这就是完全最短路径问题。w 可用一种十分类似于可用一种十分类似于 Warshall 方法的算法来生成方法的算法来生成距离矩阵距离矩阵，它被称为，它被称为 Floyd算法（算法（R.Floyd）。只要）。只要，该算法既，该算法既 应用于无向加权图，也可

21、用于有向加权图（有向路径、有向回路）。应用于无向加权图，也可用于有向加权图（有向路径、有向回路）。2671332700016123414023W 4 400010342567716112693412340D 带权有向图带权有向图 权重矩阵权重矩阵 33(0)03207016023412341D 路径中不允许包含中间顶点，路径中不允许包含中间顶点，即权重矩阵。框起来的行和列即权重矩阵。框起来的行和列用于计算后继矩阵用于计算后继矩阵 ：(1)03207130 12659 04D 路径中允许包含编号不大于路径中允许包含编号不大于1的中间顶点。的中间顶点。新增新增2条路径：条路径：4 3, 2 3。框

22、内元素计算。框内元素计算。3, 1=2+7=9。：路径中允许包含编号不大于路径中允许包含编号不大于2的中间顶点。的中间顶点。新增新增1条路径：条路径：3 1。框内元素计算。框内元素计算 。为何为何D(2)3, 3=0，非，非7+5=12？路径？路径3213对角元对角元=0，自己到自己距离最短。所以，自己到自己距离最短。所以， 此元素不被改写。此元素不被改写。26713(2)3 903205716901204D 34路径中允许包含编号不大于路径中允许包含编号不大于3的中间顶点。的中间顶点。新增新增2条路径条路径1 2，4 2。框内元素计算。框内元素计算 。(3)03205970123412361

23、901046416D 26713路径中允许包含编号不大于路径中允许包含编号不大于4的中间顶点。的中间顶点。没有新增路径，有一条更短路径：没有新增路径，有一条更短路径：3 1。问：下划线元素为什么没有被改写？问：下划线元素为什么没有被改写？(4)7010342056701616901234D ;()(1)(1) , ,(1. ,1. )1min, , /k/, ;/DWinfortodofortodofortodorejnD i jD i jD i kD k jDFloyd WnnWWurnknt 输输入入权权重重矩矩阵阵也也可可直直接接改改写写，此此步步省省略略级级 循循环环行行循循环环列列循

24、循环环返返回回传传递递闭闭包包立方级算法立方级算法35前面我们已经讲过前面我们已经讲过BST的相关算法及特性，本节介绍什么是最优的相关算法及特性，本节介绍什么是最优 BST，以及用动态规划算法来构造以及用动态规划算法来构造 BST。：基于统计先验知识，我们可统计出一个数表（集合）中：基于统计先验知识，我们可统计出一个数表（集合）中 各元素的各元素的，理解为集合各元素的，理解为集合各元素的出现频率出现频率。比如中文输入法。比如中文输入法 字库中各词条（单字、词组等）的字库中各词条（单字、词组等）的先验概率先验概率，针对用户习惯可以自动，针对用户习惯可以自动 调整词频调整词频所谓动态调频、所谓动态

25、调频、高频先现高频先现原则，以减少用户翻查次数。原则，以减少用户翻查次数。 这就是这就是：查找过程中键值比较次数最少，或者说：查找过程中键值比较次数最少，或者说 希望希望。为解决这样的。为解决这样的 问题，显然需要对集合的每个元素赋予一个特殊属性问题，显然需要对集合的每个元素赋予一个特殊属性 查找概率。查找概率。： 最优最优BST整棵树的整棵树的最小。最小。BST 好处是查找效率高，好处是查找效率高， 平均查找效率属于平均查找效率属于logn型，最坏为线性（完全不平衡）。型，最坏为线性（完全不平衡）。36w 已知已知：4个键个键 a1, a2, a3, a4 ，出现概率依次为，出现概率依次为

26、0.1, 0.2, 0.4, 0.3 w 要求要求：构造包含这：构造包含这4个键的最优个键的最优BST。w 策略策略：生成包含生成包含4个键的个键的，共，共14种。然后计算每个种。然后计算每个BST的的 平均键值比较次数平均键值比较次数，从中选择比较次数最小的作为最优，从中选择比较次数最小的作为最优BST。 包含包含 n 个键的个键的BST总数等于第总数等于第 n 个个卡塔兰数卡塔兰数：210 ,( )1nnnc nCn 比较比较1次次比较比较2次次比较比较3次次比较比较4次次比较比较1次次比较比较2次次比较比较3次次0.11+ 0.22 + 0.43+ 0.34 = 0.21+ 0.12+

27、0.42 + 0.33 = 一定存在键值平均比较一定存在键值平均比较次数最少的最优次数最少的最优 BST。37w 问题：问题：n个键个键 ，查找概率，查找概率 ，构成最优，构成最优BST， 表示为表示为 ，求这棵树的平均查找次数，求这棵树的平均查找次数 （耗费最低）。（耗费最低）。 换言之，如何构造这棵最优换言之，如何构造这棵最优BST，使得，使得 C1, n 最小。最小。w 分段求解分段求解： 动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解 由其直接前趋实例解计算得到。对于最优由其直接前趋实例解计算得到。对于最优BST

28、问题，利用减一技术和问题，利用减一技术和 最优性原则，如果前最优性原则，如果前 个节点构成最优个节点构成最优BST， 加入一个节点加入一个节点 an 后后 要求构成规模要求构成规模 的最优的最优BST。按。按 n-1, n-2 , . , 2, 1 递归，问题可解。递归，问题可解。：C1, 2C1, 3 . 。 为不失一般性用为不失一般性用 Ci, j 表示由表示由 构成的构成的BST的耗费。其中的耗费。其中 1i j n。这棵树表示为。这棵树表示为 。，它的，它的 左子树为左子树为 ，右子树为，右子树为 。要求选择的。要求选择的 k 使得整棵树的平均查找使得整棵树的平均查找 次数次数 Ci,

29、 j最小。左右子树递归执行此过程。（最小。左右子树递归执行此过程。（）1, .,naa1, .,npp1nT, .,ijaajiTka1kiT 1jkT 381, .,ikaa 最优最优BST1, .,kjaa 最优最优BST1111, ., .,.,.,.ikkjikkkkjppappaapaa 根根左左子子树树右右子子树树键键值值：概概率率：k-1 = i：左子树缩为单节点。：左子树缩为单节点。k+1= j：右子树缩为单节点。：右子树缩为单节点。11 ,11111( ()( ()( , m)1inmi1(1)njkllrrl ir kjkllrrl irkjkkli kji kjC i k

30、rir kklp L ap L apCL ap L appjpip 整整树树平平均均左左子子树树（成成功功查查找找）右右子子树树（成成功功查查找找）左左子子树树平平均均根根全全部部节节点点概概率率和和右右子子树树 1, ,11, , minC kji kjjss iC i kCpjCki j 平平均均1i j n递推计算式递推计算式39例：例：4个键个键 a1 , a2 , a3 , a4 ，出现概率依次为，出现概率依次为 0.1, 0.2, 0.4, 0.3 ，求求：构造包含这：构造包含这4个键的最优个键的最优BST。（。（n = 4）解：计算公式如下：解：计算公式如下： 1 , ,11,

31、miniijskijjsnC i jC i kjpC k 2121,12211, 2min0.1:1,02, 200.20.420.30.5:1,13, 20.100.34kssijsskCCpCCpCk 最最优优根根31311,331311:1,00.00.2, 30.81, 371.52:1,min31, 20.4113, 30.10.40.71.2:4, 3.10.00.7ssssijsskkCpkCCpCCCkCp 最最优优根根k 是选择的根节点下标。上面是选择的根节点下标。上面 是下页的计算结果。是下页的计算结果。403232,23322:2,13, 300.2, 3min340.6

32、1.0:2, 24, 30.200.60.8ssijsskkCCpCCkCp 最最优优根根 1 , ,11, miniijskijjsnC i jC i kjpC k 计算公式：计算公式：41414114,41411:1,00.01.022,42,43,43,41,:1,10.11.03:4,40.31.01.74:5,40.01.02.4min1, 210.41, 31.1ssssijsssksCCCCkCpkCpkCpkCpCCC 434344,33:3, 24,40.031.00.30.74:3, 35,40.40.00.71.3, min14ssijkssCCpkCpCkC 最最优优根

33、根41 1 , ,11, miniijskijjsnC i jC i kjpC k 计算公式：计算公式：42422,422442:2,10.00.91.9:2, 23,41.02,44,40.20.30.94:5,40min31.42, 30.8.00.91.7ssssijsskkCpCCpkCCkCCp 最最优优根根414141,4141142,41.43,41.1:1,00.01.02.42:1,10.11.02.1:4,40.31.04:5,40.01.02.01,4min31, 20.41.71, 31.11ssssijkssssCkCpkCCCkCCpCpkCp 最最优优根根42 已

34、知已知 4个键个键 a1 , a2 , a3 , a4 ，出现概率依次为，出现概率依次为 0.1, 0.2, 0.4, 0.3 。各阶段计算结果，例如各阶段计算结果，例如 C2, 4 = ：图中箭头表示图中箭头表示的一对元素，将的一对元素，将与与(p2+p3+p4)相加相加C2,4=0.5+(0.2+0.4+0.3) = 1.4。如此计算。如此计算Ci, j, 1ijn=4。实际计算过程的实际计算过程的 i、j 范围范围 i: 1n-1，j: 2n，图中红色数字。，图中红色数字。43w 本例计算结果本例计算结果：1, .,ikaa 最优最优BST1, .,kjaa 最优最优BST1111:,

35、., .,ikkkjikkjkBSTaaaaaaaaaa 根根左左子子树树右右子子树树键键值值：根表可知，根表可知，4个键的最优根下标为个键的最优根下标为3 即即a3键。它的左子树为键。它的左子树为a1 a2键键，右子树右子树为为a4键。左子树是什么结构呢？再看根表，键。左子树是什么结构呢？再看根表， a1 a2 构成的最优子树根是构成的最优子树根是a2。因为因为a1 a2 ，所以，所以1键是键是2键的左节点。键的左节点。44 ,10; , ;( 1. , 1. , 1.1,0. , 1.1,0/, ;1, 0. )/11/2;(11)(1);C i iC i iP iR i iiOptima

36、lBST An Pn Cnn RnnC nndnindjidfortodofortodonn C C对对角角元元C C次次对对角角元元R R次次对对角角元元C C对对角角元元最最后后一一个个元元素素加加入入节节点点序序列列范范围围： 范范围围：;()() ,11, / ,11, ; , ; , ; ;(1)/;/;/minvalkijminvC i kC kjminvalkminkR i jalC i kC kjsumP isijsumskminC i jmumfortodoiffortoinvkdals mouPetsr 当当前前根根k k的的最最小小平平均均比比较较次次数数找找最最优优根根

37、基基本本操操作作记记录录最最优优根根，此此句句教教材材上上错错为为概概率率和和( 1, ,);CnnRurRi,j可以限定在可以限定在Ri,j-1和和Ri+1,j之间，效率降至之间，效率降至平方型。平方型。45已知已知：n 个重量个重量 w1,.,wn、价值、价值 v1,.,vn 的物品和一个承重量的物品和一个承重量W的背包。的背包。要求要求：找出最有价值子集，且能装入背包中（不超重）。：找出最有价值子集，且能装入背包中（不超重）。假定假定：物品重量、背包承重量、：物品重量、背包承重量、物品数量物品数量（01背包）都是整数。背包）都是整数。：求满足约束方程的是目标函数达到最大的解向量求满足约束

38、方程的是目标函数达到最大的解向量 X = (x1 , . , xn) 。穷举穷举n个物品全部组合（幂集，子集数个物品全部组合（幂集，子集数=2n），从中找出最有价值子集。），从中找出最有价值子集。贪婪法（后述）不一定能找到最优解。贪婪法（后述）不一定能找到最优解。11max( ,)nniiiiiiwWxVvnxW物品数物品数承重量承重量46 动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解 由直接前趋子实例解计算得到。对于由直接前趋子实例解计算得到。对于01背包问题，可利用减一技术和背包问题，可利用减一技术和 最优性原则，

39、按物品数量和背包承重量分段。最优性原则，按物品数量和背包承重量分段。 前前 i 个物品中最优子集的总价值（动态规划函数）：个物品中最优子集的总价值（动态规划函数）： （0个物品），个物品），（承重量（承重量0） 第第 i 个物品不能装入，个物品不能装入， j wi （不超重）（不超重） 第第1阶段：装入阶段：装入1个物品，计算各种承重量下的最优价值子集；个物品，计算各种承重量下的最优价值子集； 第第2阶段：装入阶段：装入2个物品，计算各种承重量下的最优价值子集；个物品，计算各种承重量下的最优价值子集； 第第n阶段：装入阶段：装入n个物品，计算各种承重量下的个物品，计算各种承重量下的。47前前

40、i 个物品中最优子集的总价值（动态规划函数）：个物品中最优子集的总价值（动态规划函数）： （0个物品），个物品），（承重量（承重量0） 第第 i 个物品不能装入，个物品不能装入， j wi （不超重）（不超重） 说明：可按行（或列）填写此表。说明：可按行（或列）填写此表。 48w 例：例：01背包数据如下表，求：能够放入背包的最有价值的物品集合。背包数据如下表，求：能够放入背包的最有价值的物品集合。自底向上：按行或列填表。递推公式：自底向上：按行或列填表。递推公式：444(3,5)(4,5)(3,5)(3,5)(3,3)321522maxmaxmax37VVvVwVvV (1, )max( , )(1,)iiV ijVvjwi jV i 例如：例如：接下来，找出最优解的物品集合。接下来，找出最优解的物品集合。49w 通过最优解的回溯，找出最优子集为通过最优解