《第6章动态规划法1.pptVIP

6.1.3 动态规划法的设计思想 将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。 这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。 在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。 动态规划的基本要素 最优子结构：问题的最优解是由其子问题的最优解所构成的。 重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。 动态规划的基本方法 动态规划通常可以按以下几个步骤进行： (1)找出最优解的性质，并刻画其结构特征； (2)递归地定义最优值； (3)以自底向上的方式计算出各子结构的最优值并添入表格中保存； (4)根据计算最优值时得到的信息，构造最优解。 步骤1~3是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。 算法6.2——多段图的最短路径 1．初始化：数组cost[n]初始化为最大值，数组path[n]初始化为-1； 2．for (i=n-2; i=0; i--) 2.1 对顶点i的每一个邻接点j，根据式6.7计算cost[i]; 2.2 根据式6.8计算path[i]; 3．输出最短路径长度cost[0]; 4. 输出最短路径经过的顶点： 4.1 i=0 4.2 循环直到path[i]=n-1 4.2.1 输出path[i]; 4.2.2 i=path[i]; 算法6.2主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法6.2的时间复杂性为O(n+m)。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 6.3 组合问题中的动态规划法 6.3.1 0/1背包问题 6.3.2 最长公共子序列问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 6.3.1 0/1背包问题 (The Knapsack Problem) 重量 价值 w1 v1 w2 v2 ... ... wn vn n个物品，背包容量W 最大化： 限制条件： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ? School of Computer Science and Technology, SWUST * 背包问题(The Knapsack Problem) 动态规划分析 设V[i,j]为前i个物品放到背包容量为j的背包中时最优解的物品总价值。则目标是：V[n,W]。 对于n个物品，要得到V[n,W]，有两种情况： a. 第n个物品不在背包中，则最优解物品总价值为V[n-1,W] b. 第n个物品在背包中，则最优解物品总价值为前n-1个物品的最优解总价值V[n-1,W-vn]与第n个物品价值的和，或者就是前n-1个物品的最优解总价值，这里取两个中的最大值，即V[n,W]=Max{V[n-1,W-Vn]+vn,V[n-1,W]} Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ? School of Computer Science and Technology, SWUST * 背包问题(The Knapsack Problem) 对于一般情况有： 设V[i,j]为前i个物品放到背包容量为j的背包中时最优解的物品总价值。有两种情况