背包问题之动态规划法

1、动态编程。概述，3 .图形问题中的动态规划方法。组合问题中的动态规划方法，4。发现问题的动态规划方法。概述，1.1示例(多段图)，1.4最优性原则，1.6动态规划方法的设计思想，1.5无后效原则，1.3动态规划适合解决什么样的问题？1.1多段图的最短路径问题，让图G=(V，E)是加权有向连通图。如果顶点集v被分成k个不相交的子集Vi(2kn，1ik)，从而e中的任何边(u，v)必须具有uVi，vVi m(1ik，1i mk)，那么图g被称为多段图。多段图的最短路径问题是寻找从起点到终点的最短路径。因为多段图将顶点分成k个不相交的子集，所以多段图被分成k个段，每个段包含一个顶点子集。根据多段图的

2、定义，每个子集中的顶点不相邻。不失一般性，多线段图的顶点按线段顺序编号，同一线段中顶点的相互顺序无关。假设图中的顶点数为n，源点s的个数为0，终点t的个数为n-1，并且对于图中的任何边(u，v)，顶点u的个数都小于顶点v的个数。设G为有向加权图，则G从顶点I到顶点J的最短路径问题满足最优性原则。证明了iipiqj是最短路径，但子路径ipiqj不是最优的。假设最优路径是ipiqj，我们重构了一条路径：iipiqj的路径长度明显比iipiqj短，这与iipiqj是从顶点I到顶点j的最短路径的假设相矛盾。因此，原问题满足最优性原则。对于多段图的边(u，v)，边上的权重用cuv表示，从源点s到终点t的

3、最短路径表示为d(s，t)，因此从源点0到终点9的最短路径d (0，9)由以下公式确定：d(0，9)=minc01d (1，9)，c02d()。和d (1，9)=minc14d (4，9)，c15d (5，9) d(2，9)=minc24d (4，9)，c25d (5，9) 9)这一阶段的决定取决于d (4，9)，d (5，9)和d(6，9)的计算结果：d (4，9)=minc47d (7，9)，c48d (8，9) d (5，9)=minc57d()。9)此阶段的决策取决于d(7，9)和d(8，9)的计算，这可以直接获得(决策引起的状态转换在括号中给出):d(7，9)=C797 (79) d

4、(8，9)=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)=minc4 c26 d(6，9)=min6 9，7 9，8 8=15(24) d(1，9)=minc14 d(4，9)，c15 d(5，9)=min99，89=17 (15) d (0，9)=minc01d (1，9)，c02d (2，9)，c03d (3，9)=min417，215，313=16 (03)，最短路径为0353。 在上例的多阶段决策问题中，每个阶段所做的决策通常与时间有关，时间取决于当前状态，然后导致状态转换。一个决

5、策序列是在变化的状态下产生的，因此它具有“动态”的含义，这就是求解多阶段决策优化问题的动态规划方法。1.2什么是动态规划？动态规划是运筹学的一个分支。动态规划与其说是一种算法，不如说是一种思维方法。因为动态规划没有固定的框架，即使它应用于同一问题，也可以建立各种求解算法。许多关于隐式图的算法，如Dijkstra算法和广度优先搜索算法，都渗透着动态规划的思想。因此，动态规划不能首先提供一组模式，如深度或广度，而可以在需要时使用；它必须分析和处理具体的问题，它需要丰富的想象力来建立模型和创造性的想法来解决它们。确切地说，动态规划不是万能的，它只适用于在一定条件下求解最优策略问题。也许，每个人听到这

6、个结论都会失望：事实上，这个结论并没有降低动态规划的光辉，因为在上述范围内有许多问题，而许多似乎不在这个范围内的问题可以转化为这样的问题。上述“满足一定条件”主要指以下两点：(1)状态必须满足最优化原则；(2)国家不得满足任何后果。这个特性意味着什么？表明动态规划适合解决当前决策与过去状态无关的问题。国家，出现在战略的任何位置，具有相同的地位，可以执行相同的决定。这就是无后遗症的含义。1.3动态规划适合解决什么样的问题，作为整个过程的最优策略，具有以下性质：不管过去的状态和决策，对于由以前的决策形成的当前状态，剩余的决策必须构成最优策略。一般认为，子问题的局部优化将导致整个问题的全局优化，即问

7、题具有最优子结构的性质，即问题的最优解只依赖于子问题的最优解，非最优解对问题的解没有影响。在示例1中的最短路径问题中，从A到E的最佳路径上的任何点到端点E的路径也必须是从该点到端点E的最佳路径，这满足优化原则。让我们讨论另一个问题。1.4最优性原则，示例中具有最小余数的路径，分析在此问题中，如果按照示例1中的方法求解，将会出现错误。根据示例1的思想，A的最佳值可以由B的最佳值来确定，B的最佳值是(1 3) mod 4=0，因此A的最佳值应该是2。事实上，路径C1C3C5的最佳值是(2 1 1) mod 4=0，所以最佳路径B不是最佳路径A的子路径，也就是说，最佳路径A的值不是。可以看出，不是所

8、有的“决策问题”都可以用“动态规划”来解决，而应用“动态规划”来处理问题必须满足最优化原则。所谓无后效原则是指这样一种性质，即一旦某一阶段的状态被确定，其后过程的演变就不再受先前状态和决定的影响。也就是说，“未来与过去无关”，而当前状态是对以往历史的完整总结，它只能通过当前状态影响未来进程的演变。具体地说，如果把一个问题分成不同的阶段，第一阶段的状态只能从第一阶段的状态通过状态转移方程得到，而状态转移方程与其他状态无关，特别是没有发生的状态，即没有后效。1.5无后效原则，1.6动态规划法的设计思想，它将待解决的问题分解成几个相互重叠的子问题，每个子问题对应一个阶段的决策过程。一般来说，子问题的

9、重叠关系表现为求解给定问题(即动态规划函数)的递归关系，子问题的解被求解一次并填入表中。当需要再次求解该子问题时，可以通过查表得到子问题。为了达到这个目的，可以用一个表来记录所有已求解子问题的解，这就是动态规划法的设计思想。具体的动态编程方法是多种多样的，但是它们有相同的填写表单的形式。1.根据问题的时间或空间特征，将问题分成几个阶段。第二，选择状态：用不同的状态表达问题发展到每个阶段时的各种客观情况。第三，确定决策并写出状态转移方程：状态转移是根据前一阶段的状态和决策推导出该阶段的状态。4.编写编程方程(包括边界条件):动态编程的基本方程是编程方程的一般形式表达式。动态规划算法的基本步骤是，

10、用动态规划方法求解的问题不仅可以分解成几个重叠的子问题，而且满足最优性原则(也称最优子结构性质)，它具有以下特点：该问题的最优解也包含其子问题的最优解。在分析一个问题是否满足最优性原则时，通常假设由问题的最优解导出的子问题的解不是最优的，然后说明在这种假设下可以构造出比原问题的最优解更好的解，这就导致了矛盾。动态规划方法利用最优性原理，从子问题的最优解开始，自下而上地逐步构造出整个问题的最优解。动态规划法的算法设计一般分为三个阶段：(1)分段：将原问题分解成若干个重叠的子问题；(2)分析：分析问题是否满足最优性原则，找出动态规划函数的递推公式；(3)解决方案：采用递归自底向上计算实现动态规划过

11、程。2。组合问题中的动态规划方法，2.1 0/1背包问题，2.2最长公共子序列问题，2.1 0/1背包问题，给定N个物品和一个背包，物品I的重量为wi，其值为vi，背包的容量为c。背包问题是如何选择背包中的物品，使背包中物品的总价值最大化。如果在选择要装入背包的物品时，每个物品I只有两种选择：打包还是不打包，即多次将物品I装入背包还是只将物品I的一部分装入背包，则称之为0/1背包问题。在0/1背包问题中，物品1要么被装进背包，要么没有。让xi指出物品I被装入背包，然后当xi=0时，它意味着物品I没有被装入背包，当xi=1时，它意味着物品I被装入背包。根据问题的要求，有以下约束和目标函数：(公式

12、1)和(公式2)。问题归结为找到满足约束条件公式1并最大化目标函数公式2的解向量x=(x1，x2，xn)。首先，证明了0/1背包问题满足最优性原则。设(x1，x2，xn)是给定的0/1背包问题的最优解，那么(x2，xn)是下列子问题的最优解：否则，设(y2，yn)是上述子问题的最优解。因此，这表明(x1，y2，yn)比(x1，x2，xn)更好地解决了给定的0/1背包问题，这导致了矛盾。0/1背包问题可以看作一个决策序列(x1，x2，xn)，任何变量xi的决策是xi=1还是xi=0。xi-1确定后，(x1，xi-1)已经确定。当xi被决定时，问题处于以下两种状态之一：a .如果背包容量不足以装载

13、物品I，则xi=0的背包不会增加其价值；b .如果背包的容量可以装载物品I，则xi=1的背包的价值将增加vi。在这两种情况下，最大的背包价值应该是xi决定后的背包价值。让V(i，j)代表在第一个i(1in)项目中能够装载到具有j(1jC)容量的背包中的项目的最大值，那么可以获得以下动态编程函数：V(i，0)=V(0，j)=0(等式3)，其示出了第一个I项目被装载到具有0容量的背包中，并且0个项目被装载到容量中。公式4的第一个公式表明，如果第I个物品的重量大于背包的容量，则装载第一个I个物品获得的最大值与装载第一个i-1个物品获得的最大值相同，即物品I不能装载到背包中；第二个公式表明，如果第I个

14、物品的重量小于背包的容量，将会出现以下两种情况：(1)如果第I个物品被放入背包，背包中物品的价值等于将第i-1个物品放入容量为j-wi的背包中的价值加上第I个物品的价值；(2)如果背包中没有装载第I个物品，则背包中物品的价值等于将第i-1个物品装载到容量为j的背包中所获得的价值。显然，两者中较高的价值被认为是将第I个物品装载到背板中的最佳解决方案(公式4)在第一阶段，仅装载第一个项目，以确定背包在各种条件下可以获得的最大值；在第二阶段，仅装载前两个项目，以确定背包在各种条件下可以获得的最大值；以此类推，直到第n阶段。最后，V(n，C)是当n个物品装载在容量为C的背包中时获得的最大值。要确定要装

15、载到背包中的特定物品，从V(n，C)的值向前推。如果V(n，C)V(n-1，C)，则意味着第n个项目被装载到背包中，第n-1个项目被装载到容量为C-wn的背包中；否则，第n个项目不被装载到背包中，并且第n-1个项目被装载到具有容量c的背包中。以此类推，直到确定第一个项目是否被包装在背包中。因此，可以获得以下函数：(等式5)，例如，有五个项目，其重量分别为2、2、6、5、4，并且值分别为6、3、5、4、6，并且背包的容量为10，以便找到背包中装载的项目并获得最大值。根据动态规划函数，用(n 1)(C 1)的二维表v，Vij表示将第一个I项装入容量为j的背包中得到的最大值，根据公式3将表的第0行和

16、第0列初始化为0，然后逐行计算Vij，如图3所示。10，12，12，可以看出背包中物品的最大值是15，根据公式5，背包中的物品是X=1，1，0，0，1。图3 0/1背包求解(填写表格)过程，假设n个项目的权重存储在数组wn中，值存储在数组vn中，背包容量为c，数组Vn 1C 1存储迭代结果，其中Vij表示通过将前I个项目加载到具有容量j的背包中获得的最大值，数组xn存储加载到背包中的项目。用动态规划方法求解0/1背包问题的算法如下：2.2最长公共子序列问题，给定序列X=(x1，x2，xm)和序列Z=(z1，z2，zk)，当且仅当存在严格递增的下标序列(i1，i2，ik)时，Z是X的子序列，因此对于所有j=1，2，k，zj=xij(