第6章-动态规划法ppt课件.ppt

《第6章-动态规划法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章-动态规划法ppt课件.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第6章章 动态规划法动态规划法教学内容教学内容动态规划的定义及历史动态规划求解问题的步骤动态规划计算二项式系数图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法要求要求 掌握动态规划的思想及文体求解步骤，掌握动态规划求解常见问题如：每对节点间的最短距离、最优二分检索树、背包问题等中的应用。第第6章章 动态规划法动态规划法 6.5 实验项目实验项目最大子段和问题最大子段和问题6.4 查找问题中的动态规划法查找问题中的动态规划法6.3 组合问题中的动态规划法组合问题中的动态规划法6.1 概概 述述 6.2 图问题中的动态规划法图问题中的动态规划法6.1 概概 述述 6.1.1 最

2、优化问题最优化问题 6.1.2 最优性原理最优性原理6.1.3 动态规划法的设计思想动态规划法的设计思想约束条件约束条件：有有n个输入，它的解由这个输入，它的解由这n个输入的一个子集组成，个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为这个子集必须满足某些事先给定的条件，这些条件称为约束条约束条件件可行解：可行解：满足约束条件的解称为问题的满足约束条件的解称为问题的可行解可行解目标函数：目标函数：满足约束条件的可行解可能不只一个，为了衡量满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函这些可行解的优劣，事先给出一定的标准，这

3、些标准通常以函数的形式给出，这些标准函数称为数的形式给出，这些标准函数称为目标函数目标函数最优解：最优解：使目标函数取得极值（极大或极小）的可行解称为使目标函数取得极值（极大或极小）的可行解称为最优解最优解最优化问题：最优化问题：这类问题就称为这类问题就称为最优化问题最优化问题 6.1.1 最优化问题最优化问题什么是最优化问题？什么是最优化问题？例：例：自动柜员机（自动柜员机（POS机）付款问题：机）付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。 假定POS机中有n张面值为pi(1in)的货币，用集合P=p1, p2, , pn表示，如果POS机需支付的现金为A，那么，它必须

4、从P中选取一个最小子集S，使得 （式6.1）miiiSmApSp1|)|(,向量X=( x1, x2, , xn)表示S中所选取的货币，则 （式6.2） SpSpxiii01POS机支付的现金必须满足 （式6.3）Apxniii 1 并且 （式6.4） niixd1min集合集合P：问题的输入问题的输入可行解：可行解：满足式满足式6.1的解称为可行解的解称为可行解解的表现形式：解的表现形式：式式6.2是解的表现形式，因为向量是解的表现形式，因为向量X中有中有n个个元素，每个元素的取值为元素，每个元素的取值为0或或1，所以，可以有，所以，可以有2n个不同的个不同的向量，所有这些向量的全体构成该问

5、题的解空间向量，所有这些向量的全体构成该问题的解空间约束条件：约束条件：式式6.3是该问题的约束条件是该问题的约束条件目标函数：目标函数：式式6.4是该问题的目标函数是该问题的目标函数最优解：最优解：使式使式6.4取得极小值的解称为该问题的最优解取得极小值的解称为该问题的最优解 6.1.2 最优性原理最优性原理 多阶段决策：多阶段决策：n 对于一个具有对于一个具有n n个输入个输入的最优化问题，其求解的最优化问题，其求解过程往往可以划分为过程往往可以划分为若干个阶段若干个阶段n 每一阶段的每一阶段的决策决策仅依赖于前一阶段的仅依赖于前一阶段的状态状态，由，由决策所采取的动作使状态发生转移，成为

6、下一阶段决策所采取的动作使状态发生转移，成为下一阶段决策的依据决策的依据n 一个一个决策序列决策序列在不断变化的状态中产生在不断变化的状态中产生S0P1P2Pn 多阶段决策过程多阶段决策过程S1S2Sn-1Sn分析最优化问题！分析最优化问题！Sn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1 sn-1,kn-1pn,knpn-1,kn-1动态规划的决策过程动态规划的决策过程sn-1,1sn-1,rn-1sn,1sn,rn School of Computer Science and Technology, SWUST 9 最优性原理最优性原理(Principle of

7、 Optimality) 无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。重要结论：重要结论： 一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有解决该问题。 而解决问题的关键在于获取各阶段问的递推关系式（动态规划函数）动态规划函数）。6.1.3 动态规划法的设计思想动态规划法的设计思想 将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。 这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为

8、了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。 在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。 原问题的解 原问题 填 表子问题1子问题2子问题n动态规划法的求解过程分治法：分治法：n=5时计算斐波那契数的过程 F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：例：计算斐波那契数：2)2() 1(1100)(nnFnFnnnF01234567890112358132134求解斐波那契数F(9)的填表过程 ：动态规划法：动态

9、规划法：分析：分析：计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。 动态规划的基本要素 最优子结构：问题的最优解是由其子问题的最优解所构成的。 重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。如何证明问题是否满足最优性原理？如何证明问题是否满足最优性原理？用反证法！ 先假设由问题的最优解导出的子问题的解不是最优的; 然后再证明在这个假设下可构造

10、出比原问题最优解更好的解，从而导致矛盾。 动态规划的基本方法 动态规划通常可以按以下几个步骤进行： (1)找出最优解的性质，并刻画其结构特征； (2)递归地定义最优值； (3)以自底向上的方式计算出各子结构的最优值并添入表格中保存； (4)根据计算最优值时得到的信息，构造最优解。 步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。6.2 图问题中的动态规划法图问题中的动态规划法 6.2.1 TSP问题问题 6.2.2 多段图的最短路径问题多段图的最短路径问题6.2.1 TSP问题问题 TSPTSP问题：问题：旅行家要旅行旅行家要旅

11、行n个城市，要求各个城市个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走经历且仅经历一次然后回到出发城市，并要求所走的的路程最短路程最短。 各个城市间的距离可以用代价矩阵来表示。各个城市间的距离可以用代价矩阵来表示。0321C= 3 6 7 5 2 3 6 4 2 3 7 5 带权图的代价矩阵带权图的代价矩阵 设s, s1, s2, , sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径最短路径，显然s1, s2, , sp, s一定构成一条从s1到s的最短路径最短路径。 如若不然，设s1, r1, r2, ,

12、 rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, , rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, , sp, s要短，从而导致矛盾。 所以，TSP问题满足最优性原理。证明证明TSP问题满足最优性原理问题满足最优性原理构造动态规划函数：构造动态规划函数： 假设从顶点i出发，令d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度 开始时，VVi， 于是，TSP问题的动态规划函数动态规划函数为： d(i,V)=mincik+d(k,Vk)(kV) （式6.5） d(k,)=cki(ki)

13、 （式6.6）这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(

14、3, 1)=c31+d(1, ) 最后一个阶段的决策：最后一个阶段的决策：从城市从城市0出发经城市出发经城市1、2、3然后回到城市然后回到城市0的最短路径长度是：的最短路径长度是：d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2)而下式可以直接获得（括号中是该决策引起的状态转移）：而下式可以直接获得（括号中是该决策引起的状态转移）：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)

15、d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+32+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21)d(3, 1)= c31+d(1, )=7+5=12(31) 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)=min

16、c31+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, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，从顶点所以，从顶点0出发的出发的TSP问题的问题的最短路径长度为最短路径长度为10，路径路径是是01230。 u 假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，u设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发

17、点0的最短路径长度。 ji 1231, 21, 32, 31, 2, 30 1015 86 7 269 5 10 331211 14 动态规划法求解动态规划法求解TSP问题的填表过程问题的填表过程0321C= 3 6 7 5 2 3 6 4 2 3 7 5 算法6.1TSP问题 1for (i=1; in; i+) /初始化第0列 di0=ci0; 2for (j=1; j2n-1-1; j+) for (i=1; in; i+) /依次进行第i次迭代 if (子集Vj中不包含i) 对Vj中的每个元素k，计算dij=min(cik+dkj-1); 3.对V2n-1-1中的每一个元素k，计算d0

18、2n-1-1=min(c0k+dk2n-1-2); 4输出最短路径长度d02n-1-1;算法算法6.1的时间复杂性为的时间复杂性为O(2n)。蛮力法蛮力法求解求解TSP问题问题: :时间复杂性是时间复杂性是O(n!) 算法描述算法描述 设顶点之间的代价存放在数组cnn中256.2.2 多段图的最短路径问题多段图的最短路径问题 多段图多段图G(V，E)是是个有向图。它具有如下特性：个有向图。它具有如下特性： 图中的结点被划分成图中的结点被划分成k 2个不相交的集合个不相交的集合Vi ,1ik,ik,其中其中V1和和Vk分别只有一个结点分别只有一个结点s(源点源点)和和t(汇点汇点)。 图中所有的

19、边图中所有的边均具有如下性质：若均具有如下性质：若uVi ，则，则v Vi+1 ,1ik,ik,且每条边且每条边均附有成本均附有成本c(u，v)。 从从s到到t的一条路径成本是这条路径上边的成本和。的一条路径成本是这条路径上边的成本和。 多段图问题多段图问题(multistage graph problem)是求由是求由s到到t的最小成本路的最小成本路径。径。123458761110912st9732227111118654356524V1V2V3V4V52120345678949387684756866537 一个多段图一个多段图 设设s, s1, s2, , sp, t是从是从s到到t的一

20、条的一条最短路径最短路径，从源点，从源点s开始，设从开始，设从s到下一段的顶点到下一段的顶点s1已经求出，则问题转化已经求出，则问题转化为求从为求从s1到到t的最短路径，显然的最短路径，显然s1, s2, , sp, t一定构成一一定构成一条从条从s1到到t的的最短路径最短路径。 如若不然，如若不然， 设设s1, r1, r2, , rq, t是一条从是一条从s1到到t的最短路径，则的最短路径，则s, s1, r1, r2, , rq, t将是一条从将是一条从s到到t的路径且比的路径且比s, s1, s2, , sp, t的路径长度要短，的路径长度要短，从而导致矛盾从而导致矛盾。 所以，多段图

21、的最短路径问题满足所以，多段图的最短路径问题满足最优性原理最优性原理。 证明多段图问题满足最优性原理证明多段图问题满足最优性原理对多段图的边对多段图的边(u, v)，用，用cuv表示边上的权值，将从源点表示边上的权值，将从源点s到终点到终点t的的最短路径记为最短路径记为d(s, t)，则从源点，则从源点0到终点到终点9的最短路径的最短路径d(0, 9)由下式由下式确定：确定：d d(0, 9)=min(0, 9)=minc c0101+ +d d(1, 9), (1, 9), c c0202+ +d d(2, 9), (2, 9), c c0303+ +d d(3, 9)(3, 9)这一阶段的

22、决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d d(1, 9)=min(1, 9)=minc c1414+ +d d(4, 9), (4, 9), c c1515+ +d d(5, 9)(5, 9)d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)d(3, 9)=minc35+d(5, 9), c36+d(6, 9)第一阶段求决策序列第一阶段求决策序列最后一个阶段的决策：最后一个阶段的决策：2120345678949387684756866537d(4, 9)=minc47+d(7, 9), c48+d(8, 9)d(5, 9

23、)=minc57+d(7, 9), c58+d(8, 9)d(6, 9)=minc67+d(7, 9), c68+d(8, 9)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：d(7, 9)=c797(79)d(8, 9)=c893(89)而而d(7, 9)和和d(8, 9)可以直接获得可以直接获得括号中给出了决策产生的括号中给出了决策产生的状态转移状态转移 这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：2120345678949387684756866537 一个多段图一个多段图第二阶段：迭代第二阶段：迭代再向前推导，有：再向前推导，

24、有：d(6, 9)=minc67+d(7, 9), c68+d(8, 9)=min6+7, 5+3=8(68)d(5, 9)=minc57+d(7, 9), c58+d(8, 9)=min8+7, 6+3=9(58)d(4, 9)=minc47+d(7, 9), c48+d(8, 9)=min5+7, 6+3=9(48)再向前推导，有：再向前推导，有：d(3, 9)=minc35+d(5, 9), c36+d(6, 9)=min4+9, 7+8=13(35)d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)=min6+9, 7+9, 8+8=15(

25、24)d(1, 9)=minc14+d(4, 9), c15+d(5, 9)=min9+9, 8+9=17(15)最后，有：最后，有：d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=min4+17, 2+15, 3+13=16(03) 最终，最终，得到最短路径为得到最短路径为03589，长度为，长度为16。 下面考虑多段图的最短路径问题的填表形式。下面考虑多段图的最短路径问题的填表形式。 用一个数组用一个数组costn作为存储子问题解的表格，作为存储子问题解的表格，costi表表示从顶点示从顶点i到终点到终点n-1的最短路径，数组的最短路径，数

26、组pathn存储状态，存储状态，pathi表示从顶点表示从顶点i到终点到终点n-1的路径上顶点的路径上顶点i的下一个顶点。的下一个顶点。则：则： costi=mincij+costj (ijn且顶点且顶点j是顶点是顶点i的邻接点的邻接点) （式（式6.7）pathi=使使cij+costj最小的最小的j （式（式6.8） 算法6.2多段图的最短路径 1初始化：数组costn初始化为最大值，数组pathn初始化为-1； 2for (i=n-2; i=0; i-) 2.1 对顶点i的每一个邻接点j，根据式6.7计算costi; 2.2 根据式6.8计算pathi; 3输出最短路径长度cost0;

27、4. 输出最短路径经过的顶点： 4.1 i=0 4.2 循环直到pathi=n-1 4.2.1 输出pathi; 4.2.2 i=pathi; 算法6.2主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法6.2的时间复杂性为O(n+m)。 6.3 6.3 组合问题中的动态规划法组合问题中的动态规划法 6.3.1 0/1

28、背包问题背包问题 6.3.2 最长公共子序列问题最长公共子序列问题346.3.1 0/1背包问题背包问题 (The Knapsack Problem)重量重量w1w2.wn价值价值v1v2.vnn个物品，背包容量W最大化：限制条件： School of Computer Science and Technology, SWUST 35背包问题(The Knapsack Problem) 动态规划分析 设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。则目标是：Vn,W。 对于n个物品，要得到Vn,W，有两种情况： a. 第n个物品不在背包中，则最优解物品总价值为Vn-1,W

29、b. 第n个物品在背包中，则最优解物品总价值为前n-1个物品的最优解总价值Vn-1,W-vn与第n个物品价值的和，或者就是前n-1个物品的最优解总价值，这里取两个中的最大值，即Vn,W=MaxVn-1,W-Vn+vn,Vn-1,W School of Computer Science and Technology, SWUST 36背包问题(The Knapsack Problem) 对于一般情况有： 设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。有两种情况： a. 第i个物品不在背包中，则最优解物品总价值为Vi-1,j（如果 ） b. 第i个物品在背包中，则最优解物品总

30、价值为前i-1个物品的最优解总价值Vi-1,W-vi与第i个物品价值的和，或者就是前i-1个物品的最优解总价值，这里取两个中的最大值，即Vi,j=MaxVi-1,j-Vi+vi,Vi-1,jiwj School of Computer Science and Technology, SWUST 37背包问题(The Knapsack Problem)物品重量价值1212￥2110￥3320￥4215￥承重量W=5V4,5V3,5，物品4包含在最有解中，后者由V3,3确定；V3,3V2,3，表明3不在最有解里，又因为V2,3 V1,3，物品2在最有解中，V1,2 V0,2，物品 1在最有解中。最

31、有解1,2,46.3.1 0/1背包问题背包问题 在在0/1背包问题中，物品背包问题中，物品i或者被装入背包，或者不被或者被装入背包，或者不被装入背包，设装入背包，设xi表示物品表示物品i装入背包的情况，则当装入背包的情况，则当xi=0时，时，表示物品表示物品i没有被装入背包，没有被装入背包，xi=1时，表示物品时，表示物品i被装入背被装入背包。根据问题的要求，有如下约束条件和目标函数：包。根据问题的要求，有如下约束条件和目标函数： )1 (1 , 01nixCxwiniii（式6.9）niiixv1max（式6.10）于是，问题归结为寻找一个满足约束条件式于是，问题归结为寻找一个满足约束条件

32、式6.9，并使目标，并使目标函数式函数式6.10达到最大的解向量达到最大的解向量X=(x1, x2, , xn)。证明证明0/1背包问题满足最优性原理。背包问题满足最优性原理。 设设(x1, x2, , xn)是所给是所给0/1背包问题的一个最优解，则背包问题的一个最优解，则( x2, , xn)是下面一个子问题的最优解：是下面一个子问题的最优解：)2(1 ,0112nixxwCxwiniiiniiixv2max如若不然，设如若不然，设(y2, , yn)是上述子问题的一个最优解，则是上述子问题的一个最优解，则 因此，因此， 这说明这说明(x1, y2, , yn)是所给是所给0/1背包问题比

33、背包问题比(x1, x2, , xn)更优的更优的解，从而导致矛盾。解，从而导致矛盾。 niiiniiixvyv22Cywxwniii211niiiniiiniiixvxvxvyvxv1211211 0/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1, x2, , xn)，对任，对任一变量一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，已确定了决策后，已确定了(x1, , xi-1)，在决策，在决策xi时，问题处于下列两种状态之一：时，问题处于下列两种状态之一：（1）背包容量不足以装入物品）背包容量不足以装入物品i，则，则xi=0，背

34、包不增加价值；，背包不增加价值；（2）背包容量可以装入物品）背包容量可以装入物品i，则，则xi=1，背包的价值增加了，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对这两种情况下背包价值的最大者应该是对xi决策后的背包决策后的背包价值。令价值。令V(i, j)表示在前表示在前i(1in)个物品中能够装入容量为个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规）的背包中的物品的最大值，则可以得到如下动态规划函数：划函数： V(i, 0)= V(0, j)=0 （式（式6.11）iiiiwjvwjiVjiVwjjiVjiV), 1(), 1(max), 1(

35、),(（式6.12） 式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式6.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者

36、中价值较大者作为把前i个物品装入容量为j的背包中的最优解。 根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。 0 例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。x5=1x4=0 x3=0 x2=1x1=1 012345678910 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=5 v5=6500669

37、912121515150 按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数： ), 1(),

38、(, 1), 1(), (0jiVjiVwjjjiVjiVxii（式6.13） 设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下： 算法6.30/1背包问题 int KnapSack(int n, int w , int v ) for (i=0; i=n; i+) /初始化第0列 Vi0=0; for (j=0; j=C; j+) /初始化第0行 V0j=0; for (i=1; i=n; i+) /计算第i行，进行第i次迭代 for (j=1; j=C; j+) if (j0; i-) if (VijVi-1j) xi=1; j=j-wi;else xi=0;return VnC; /返回背包取得的最大价值 在算法6.3中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的for循环，其时间性能是O(nC)，第四个for循环的时间性能是O(n)，所以，算法6.3的时间复杂性为O(nC)。