0-1背包问题之动态规划法 -

动态规划1.概述3.图问题中的动态规划法2.组合问题中的动态规划法4.查找问题中的动态规划法1.概述1.1例题（多段图）1.4最优性原理1.6动态规划法的设计思想1.5无后效性原则1.3动态规划适于解决什么样的问题1.2什么是动态规划1.1多段图的最短路径问题设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。根据多段图的定义，每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。2120345678949387684756866537图1一个多段图设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。证明：设i～ip～iq～j是一条最短路径，但其中子路径ip～iq～j不是最优的，假设最优的路径为ip～iq’～j，则我们重新构造一条路径：i～ip～iq’～j显然该路径长度小于i～ip～iq～j，与i～ip～iq～j是顶点i到顶点j的最短路径相矛盾.所以，原问题满足最优性原理。对多段图的边(u,v)，用cuv表示边上的权值，将从源点s到终点t的最短路径记为d(s,t)，则从源点0到终点9的最短路径d(0,9)由下式确定：d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}这是最后一个阶段的决策，它依赖于d(1,9)、d(2,9)和d(3,9)的计算结果，而d(1,9)=min{c14+d(4,9),c15+d(5,9)}d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=min{c35+d(5,9),c36+d(6,9)}这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)的计算结果：d(4,9)=min{c47+d(7,9),c48+d(8,9)}d(5,9)=min{c57+d(7,9),c58+d(8,9)}d(6,9)=min{c67+d(7,9),c68+d(8,9)}这一阶段的决策依赖于d(7,9)和d(8,9)的计算，而d(7,9)和d(8,9)可以直接获得（括号中给出了决策产生的状态转移）：d(7,9)=c79＝7(7→9)d(8,9)=c89＝3(8→9)再向前推导，有：d(6,9)=min{c67+d(7,9),c68+d(8,9)}=min{6+7,5+3}=8(6→8)d(5,9)=min{c57+d(7,9),c58+d(8,9)}=min{8+7,6+3}=9(5→8)d(4,9)=min{c47+d(7,9),c48+d(8,9)}=min{5+7,6+3}=9(4→8)d(3,9)=min{c35+d(5,9),c36+d(6,9)}=min{4+9,7+8}=13(3→5)d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=min{6+9,7+9,8+8}=15(2→4)d(1,9)=min{c14+d(4,9),c15+d(5,9)}=min{9+9,8+9}=17(1→5)d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=min{4+17,2+15,3+13}=16(0→3)得到最短路径为0→3→5→8→9，长度为16。在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。1.2什么是动态规划动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先搜索算法，都渗透着动态规划的思想。因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。上面所说的“满足一定条件”主要指下面两点：(1)状态必须满足最优化原理；(2)状态必须满足无后效性。这条特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。1.3动态规划适于解决什么样的问题作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。下面来讨论另外一个问题。1.4最优性原理例题余数最少的路径如图所示，有4个点，分别是A、B、C、D，相邻两点用两条连线C2k，C2k-1(1≤k≤3)表示两条通行的道路。连线上的数字表示道路的长度。定义从A到D的所有路径中，长度除以4所得余数最小的路径为最优路径。求一条最优路径。【分析】在这个问题中，如果还按照例题1中的方法去求解就会发生错误。按照例题1的思想，A的最优取值可以由B的最优取值来确定，而B的最优取值为(1+3)mod4=0，所以A的最优值应为2，而实际上，路径C1－C3－C5可得最优值为(2+1+1)mod4=0，所以，B的最优路径并不是A的最优路径的子路径，也就是说，A的最优取值不是由B的最优取值决定的，即其不满足最优化原理，问题不具有最优子结构的性质。由此可见，并不是所有的“决策问题”都可以用“动态规划”来解决，运用“动态规划”来处理问题必须满足最优化原理。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。1.5无后效性原则1.6动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规划法的设计思想。具体的动态规划法是多种多样的，但他们具有相同的填表形式。原问题的解原问题图2动态规划法的求解过程……填表子问题1子问题2子问题n一、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。二、选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。三、确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。四、写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法的基本步骤可以用动态规划法求解的问题除了能够分解为相互重叠的若干子问题外，还要满足最优性原理（也称最优子结构性质），这类问题具有如下特征：该问题的最优解中也包含着其子问题的最优解。在分析问题是否满足最优性原理时，通常先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。2.组合问题中的动态规划法2.10/1背包问题2.2最长公共子序列问题2.10/1背包问题给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分，则称为0/1背包问题。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：)1(}1,0{1nixCxwiniii（式1）niiixv1max（式2）问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1,x2,…,xn)。首先证明0/1背包问题满足最优性原理。设(x1,x2,…,xn)是所给0/1背包问题的一个最优解，则(x2,…,xn)是下面一个子问题的最优解：)2(}1,0{112nixxwCxwiniii如若不然，设(y2,…,yn)是上述子问题的一个最优解，则，且。因此，，这说明(x1,y2,…,yn)是所给0/1背包问题比(x1,x2,…,xn)更优的解，从而导致矛盾。niiiniiixvyv22Cywxwniii211niiiniiiniiixvxvxvyvxv12112110/1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：a.背包容量不足以装入物品i，则xi=0背包不增加价值；b.背包容量可以装入物品i，则xi=1背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i,j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：V(i,0)=V(0,j)=0（式3）iiiiwjvwjiVjiVwjjiVjiV}),1(),,1(max{),1(),(式3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包