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

1第第6章章 动态规划法动态规划法教学内容教学内容动态规划的定义及历史动态规划求解问题的步骤动态规划计算二项式系数图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法要求要求掌握动态规划的思想及文体求解步骤，掌握动态规划求解常见问题如：每对节点间的最短距离、最优二分检索树、背包问题等中的应用。1第6章 动态规划法教学内容1第第6章章动态规划法动态规划法6.5实验项目实验项目最大子段和问题最大子段和问题6.4查找问题中的动态规划法查找问题中的动态规划法6.3组合问题中的动态规划法组合问题中的动态规划法6.1概概述述6.2图问题中的动态规划法图问题中的动态规划法第6章 动态规划法 6.5 实验项目最大子段和问题626.1 概概 述述 6.1.1最优化问题最优化问题6.1.2最优性原理最优性原理6.1.3动态规划法的设计思想动态规划法的设计思想6.1 概 述 6.1.1 最优化问题 6.1.2 3约约束束条条件件：有有n个个输输入入，它它的的解解由由这这n个个输输入入的的一一个个子子集集组组成成，这这个个子子集集必必须须满满足足某某些些事事先先给给定定的的条条件件，这这些些条条件件称称为为约约束束条条件件可行解：可行解：满足约束条件的解称为问题的满足约束条件的解称为问题的可行解可行解目目标标函函数数：满满足足约约束束条条件件的的可可行行解解可可能能不不只只一一个个，为为了了衡衡量量这这些些可可行行解解的的优优劣劣，事事先先给给出出一一定定的的标标准准，这这些些标标准准通通常常以以函函数的形式给出，这些标准函数称为数的形式给出，这些标准函数称为目标函数目标函数最最优优解解：使使目目标标函函数数取取得得极极值值（极极大大或或极极小小）的的可可行行解解称称为为最最优解优解最优化问题：最优化问题：这类问题就称为这类问题就称为最优化问题最优化问题 6.1.1最优化问题最优化问题什么是最优化问题？什么是最优化问题？约束条件：有n个输入，它的解由这n个输入的一个子集组成，这个4例：例：自动柜员机（自动柜员机（POS机）付款问题：机）付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。假定POS机中有n张面值为pi(1in)的货币，用集合P=p1,p2,pn表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得 （式6.1）向量X=(x1,x2,xn)表示S中所选取的货币，则 （式6.2）例：自动柜员机（POS机）付款问题：向量X=(x1,x25POS机支付的现金必须满足 （式6.3）并且 （式6.4）集合集合P：问题的输入问题的输入可行解：可行解：满足式满足式6.1的解称为可行解的解称为可行解解的表现形式：解的表现形式：式式6.2是解的表现形式，因为向量是解的表现形式，因为向量X中有中有n个个元素，每个元素的取值为元素，每个元素的取值为0或或1，所以，可以有，所以，可以有2n个不同的个不同的向量，所有这些向量的全体构成该问题的解空间向量，所有这些向量的全体构成该问题的解空间约束条件：约束条件：式式6.3是该问题的约束条件是该问题的约束条件目标函数：目标函数：式式6.4是该问题的目标函数是该问题的目标函数最优解：最优解：使式使式6.4取得极小值的解称为该问题的最优解取得极小值的解称为该问题的最优解POS机支付的现金必须满足 并且 66.1.2最优性原理最优性原理多阶段决策：多阶段决策：n 对对于于一一个个具具有有n n个个输输入入的的最最优优化化问问题题，其其求求解解过过程往往可以划分为程往往可以划分为若干个阶段若干个阶段n 每每一一阶阶段段的的决决策策仅仅依依赖赖于于前前一一阶阶段段的的状状态态，由由决决策策所所采采取取的的动动作作使使状状态态发发生生转转移移，成成为为下下一一阶阶段段决策的依据决策的依据n 一个一个决策序列决策序列在不断变化的状态中产生在不断变化的状态中产生S0P1P2Pn多阶段决策过程多阶段决策过程S1S2Sn-1Sn分析最优化问题！分析最优化问题！6.1.2 最优性原理 多阶段决策：S0P1P2Pn 7Sn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1 sn-1,kn-1pn,knpn-1,kn-1动态规划的决策过程动态规划的决策过程sn-1,1sn-1,rn-1sn,1sn,rnSn-1SnS1S0s1,1sn,knp1,1s1,k1p18 School of Computer Science and Technology,SWUST 9最优性原理最优性原理(Principle of Optimality)无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。重要结论：重要结论：一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能可能可能可能解决该问题。而解决问题的关键在于获取各阶段问的递推关系式（动态规划函数）动态规划函数）。School of Computer Science a96.1.3 动态规划法的设计思想动态规划法的设计思想将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。6.1.3 动态规划法的设计思想将原问题分解为若干个子问题10 原问题的解 原问题 填 表子问题1子问题2子问题n动态规划法的求解过程 原问题的解 原问题 填 表子问题1子11分治法：分治法：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)例：计算斐波那契数：例：计算斐波那契数：分治法：n=5时计算斐波那契数的过程 F(5)F(4)F(31201234567890112358132134求解斐波那契数F(9)的填表过程：动态规划法：动态规划法：分析：分析：计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。01234567890112358132134求解斐波那契数13动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优14如何证明问题是否满足最优性原理？如何证明问题是否满足最优性原理？用反证法！先假设由问题的最优解导出的子问题的解不是最优的;然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。如何证明问题是否满足最优性原理？15动态规划的基本方法动态规划通常可以按以下几个步骤进行：(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值；(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；(4)根据计算最优值时得到的信息，构造最优解。步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。动态规划的基本方法动态规划通常可以按以下几个步骤进行：166.2图问题中的动态规划法图问题中的动态规划法6.2.1TSP问题问题6.2.2多段图的最短路径问题多段图的最短路径问题6.2 图问题中的动态规划法 6.2.1 TSP问题 6176.2.1TSP问题问题TSPTSP问题：问题：旅行家要旅行旅行家要旅行n个城市，要求各个城市个城市，要求各个城市经历且且仅经历一次然后回到出一次然后回到出发城市，并要求所走城市，并要求所走的的路程最短路程最短。各个城市各个城市间的距离可以用代价矩的距离可以用代价矩阵来表示。来表示。0321C=367523642375带权图的代价矩阵带权图的代价矩阵6.2.1 TSP问题 TSP问题：旅行家要旅行n18 设s,s1,s2,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径最短路径，显然s1,s2,sp,s一定构成一条从s1到s的最短路径最短路径。如若不然，设s1,r1,r2,rq,s是一条从s1到s的最短路径且经过n-1个不同城市，则s,s1,r1,r2,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,sp,s要短，从而导致矛盾。所以，TSP问题满足最优性原理。证明证明TSP问题满足最优性原理问题满足最优性原理 设s,s1,s2,sp,s是从s出发的19构造动态规划函数：构造动态规划函数：假设从顶点i出发，令d(i,V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度 开始时，VVi，于是，TSP问题的动态规划函数动态规划函数为：d(i,V)=mincik+d(k,Vk)(kV)（式6.5）d(k,)=cki(ki)（式6.6）构造动态规划函数：20这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：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(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)这一阶段的决策又依赖于下面的计算结果：最后一个阶段的决策：而21再向前倒推，有：再向前倒推，有：d(1,2)=c12+d(2,)=2+6=8(12)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)=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,1,3),c03+d(3,1,2)=min3+7,6+10,7+14=10(01)所所以以，从从顶顶点点0出出发发的的TSP问问题题的的最最短短路路径径长长度度为为10，路路径径是是01230。再向前倒推，有：d(3,1,2)=minc31+d22u 假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，u设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。ji1231,21,32,31,2,30101586726951033121114动态规划法求解动态规划法求解TSP问题的填表过程问题的填表过程0321C=367523642375 假设n个顶点用0n-1的数字编号，首先生成1n-1个元23算法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，计算d02n-1-1=min(c0k+dk2n-1-2);4输出最短路径长度d02n-1-1;算法算法6.1的时间复杂性为的时间复杂性为O(2n)。蛮力法蛮力法求解求解TSP问题问题:时间复杂性是时间复杂性是O(n!)算法描述算法描述 设顶点之间的代价存放在数组cnn中算法6.1TSP问题伪代码算法6.1的时间复杂性为O(224256.2.2 多段图的最短路径问题多段图的最短路径问题多段图多段图G(V，E)是是个有向图。它具有如下特性：个有向图。它具有如下特性：图中的结点被划分成图中的结点被划分成k 2个不相交的集合个不相交的集合Vi ,1ik,ik,其中其中V1和和Vk分分别只有一个结点别只有一个结点s(源点源点)和和t(汇点汇点)。图中所有的边图中所有的边均具有如下性质：若均具有如下性质：若uVi，则，则v Vi+1,1ik,ik,且每条边且每条边均附有成本均附有成本c(u，v)。从从s到到t的一条路径成本是这条路径上边的成本和。的一条路径成本是这条路径上边的成本和。多段图问题多段图问题(multistage graph problem)是求由是求由s到到t的最小成本路的最小成本路径。径。123458761110912st9732227111118654356524V1V2V3V4V5256.2.2 多段图的最短路径问题多段图G(V，E)是252120345678949387684756866537一个多段图一个多段图2120345678949387684756866537 26 设设s,s1,s2,sp,t是从是从s到到t的一条的一条最短路径最短路径，从源点，从源点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的路径长度要短，的路径长度要短，从而导致矛盾从而导致矛盾。所以，多段图的最短路径问题满足所以，多段图的最短路径问题满足最优性原理最优性原理。证明多段图问题满足最优性原理证明多段图问题满足最优性原理 设s,s1,s2,sp,t是从s到t的一27对多段图的边对多段图的边(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)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：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)第一阶段求决策序列第一阶段求决策序列最后一个阶段的决策：最后一个阶段的决策：2120345678949387684756866537一个多段图一个多段图对多段图的边(u,v)，用cuv表示边上的权值，将从源点s28d(4,9)=minc47+d(7,9),c48+d(8,9)d(5,9)=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一个多段图一个多段图d(4,9)=minc47+d(7,9),c48+d29第二阶段：迭代第二阶段：迭代再向前推导，有：再向前推导，有：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(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。第二阶段：迭代30下面考虑多段图的最短路径问题的填表形式。下面考虑多段图的最短路径问题的填表形式。用一个数组用一个数组costn作为存储子问题解的表格，作为存储子问题解的表格，costi表表示从顶点示从顶点i到终点到终点n-1的最短路径，数组的最短路径，数组pathn存储状态，存储状态，pathi表示从顶点表示从顶点i到终点到终点n-1的路径上顶点的路径上顶点i的下一个顶点。的下一个顶点。则：则：costi=mincij+costj(ijn且顶点且顶点j是顶点是顶点i的邻接点的邻接点)（式（式6.7）pathi=使使cij+costj最小的最小的j（式（式6.8）下面考虑多段图的最短路径问题的填表形式。31算法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;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.2多段图的最短路径伪代码 算法6.2主要由326.3 6.3 组合问题中的动态规划法组合问题中的动态规划法 6.3.10/1背包问题背包问题6.3.2最长公共子序列问题最长公共子序列问题6.3 组合问题中的动态规划法 6.3.1 0/1背包问33346.3.1 0/1背包问题背包问题(The Knapsack Problem)重量重量w1w2.wn价值价值v1v2.vnn个物品，背包容量W最大化：限制条件：346.3.1 0/1背包问题(The Knapsack34 School of Computer Science and Technology,SWUST 35背包问题(The Knapsack Problem)动态规划分析设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。则目标是：Vn,W。对于n个物品，要得到Vn,W，有两种情况：a.第n个物品不在背包中，则最优解物品总价值为Vn-1,Wb.第n个物品在背包中，则最优解物品总价值为前n-1个物品的最优解总价值Vn-1,W-vn与第n个物品价值的和，或者就是前n-1个物品的最优解总价值，这里取两个中的最大值，即Vn,W=MaxVn-1,W-Vn+vn,Vn-1,W School of Computer Science a35 School of Computer Science and Technology,SWUST 36背包问题(The Knapsack Problem)对于一般情况有：设Vi,j为前i个物品放到背包容量为j的背包中时最优解的物品总价值。有两种情况：a.第i个物品不在背包中，则最优解物品总价值为Vi-1,j（如果 ）b.第i个物品在背包中，则最优解物品总价值为前i-1个物品的最优解总价值Vi-1,W-vi与第i个物品价值的和，或者就是前i-1个物品的最优解总价值，这里取两个中的最大值，即Vi,j=MaxVi-1,j-Vi+vi,Vi-1,j School of Computer Science a36 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在最有解中。最有解1,2,4 School of Computer Science a376.3.10/1背包问题背包问题在在0/1背背包包问问题题中中，物物品品i或或者者被被装装入入背背包包，或或者者不不被被装装入入背背包包，设设xi表表示示物物品品i装装入入背背包包的的情情况况，则则当当xi=0时时，表表示示物物品品i没没有有被被装装入入背背包包，xi=1时时，表表示示物物品品i被被装装入入背背包。根据问题的要求，有如下约束条件和目标函数：包。根据问题的要求，有如下约束条件和目标函数：（式6.9）（式6.10）于是，问题归结为寻找一个满足约束条件式于是，问题归结为寻找一个满足约束条件式6.9，并使目标，并使目标函数式函数式6.10达到最大的解向量达到最大的解向量X=(x1,x2,xn)。6.3.1 0/1背包问题 在0/1背包问题38证明证明0/1背包问题满足最优性原理。背包问题满足最优性原理。设设(x1,x2,xn)是是所所给给0/1背背包包问问题题的的一一个个最最优优解解，则则(x2,xn)是下面一个子问题的最优解：是下面一个子问题的最优解：如若不然，设如若不然，设(y2,yn)是上述子问题的一个最优解，则是上述子问题的一个最优解，则 因此，因此，这说明这说明(x1,y2,yn)是所给是所给0/1背包问题比背包问题比(x1,x2,xn)更优的更优的解，从而导致矛盾。解，从而导致矛盾。证明0/1背包问题满足最优性原理。如若不然，设(y2,39 0/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1,x2,xn)，对任，对任一变量一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，已确定了决策后，已确定了(x1,xi-1)，在决策，在决策xi时，问题处于下列两种状态之一：时，问题处于下列两种状态之一：（1）背包容量不足以装入物品）背包容量不足以装入物品i，则，则xi=0，背包不增加价值；，背包不增加价值；（2）背包容量可以装入物品）背包容量可以装入物品i，则，则xi=1，背包的价值增加了，背包的价值增加了vi。这这两两种种情情况况下下背背包包价价值值的的最最大大者者应应该该是是对对xi决决策策后后的的背背包包价价值值。令令V(i,j)表表示示在在前前i(1in)个个物物品品中中能能够够装装入入容容量量为为j（1jC）的的背背包包中中的的物物品品的的最最大大值值，则则可可以以得得到到如如下下动动态态规规划函数：划函数：V(i,0)=V(0,j)=0（式（式6.11）（式6.12）0/1背包问题可以看作是决策一个序列(x1,x2,40 式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的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。式6.11表明：把前面i个物品装入容量为0的背包和把41 根据动态规划函数，用一个(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=101234567891000000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=6500669912121515150 根据动态规划函数，用一个(n+1)(C+1)的二维表42 按下述方法来划分阶段：第一阶段，只装入前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个物品是否被装入背包中为止。由此，得到如下函数：（式6.13）按下述方法来划分阶段：第一阶段，只装入前1个物品，确43 设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)。算法6.30/1背包问题C+描述 在算法6.3中45