第4章-动态规划PPT.pptVIP

最优子结构性质分析 假设（x1, x2,…, xn)是所给0-1背包问题的一个最优解，则（x2,…, xn）是下面相应子问题的一个最优解： 约束条件： 目标函数： 运用反证法来证明 建立最优值的递归关系式 令C[i][j]= C[0][j]=C[i][0]=0 （4-10) （4-11) 算法设计——求装入背包的最大价值 步骤1：设计算法所需的数据结构。采用数组w[n]来存放n个物品的重量；数组v[n]来存放n个物品的价值，背包容量为W，数组C[n+1][W+1]来存放每一次迭代的执行结果；数组x[n]用来存储所装入背包的物品状态； 步骤2：初始化。按式(4-10)初始化数组C； 步骤3：循环阶段。按式（4-11）确定前i个物品能够装入背包的情况下得到的最优值； 步骤3-1：i=1时，求出C[1][j]，1≤j≤W； 步骤3-2：i=2时，求出C[2][j]，1≤j≤W； 依此类推，直到…… 步骤3-n：i=n时，求出C[n][W]。此时，C[n][W]便是最优值； 算法设计与分析 授课教师：王秋芬 办公地点：7307 Email: w_qiufen@163.com 第四章 动态规划 目录 概述 矩阵连乘问题 凸多边形最优三角剖分 最长公共子序列问题 加工顺序问题 0-1背包问题 最优二叉查找树 教学目标 理解动态规划的思想 掌握动态规划、分治法及贪心法的异同 掌握动态规划的基本要素 掌握动态规划的设计步骤 通过实例学习，掌握动态规划设计的策略 学习动态规划的意义 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。 动态规划算法通常用于求解具有某种最优性质的问题， 动态规划的基本思想 基本思想 适合采用动态规划法求解的问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。这样就避免了大量的无意义的重复计算，从而降低算法的时间复杂性。如何对已解决的子问题的解进行保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都将其计算结果填入该表，需要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式。（参考【例4-1】） 矩阵连乘 问题描述 给定n个矩阵{A1,A2,A3,…,An}，其中Ai与Ai+1(i=1,2,3, …,n-1)是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。 以【例4-2】为例讲述 最优子结构性质分析 建立最优值的递归关系式 AiAi+1…Aj矩阵连乘，其中矩阵Am的行数为pm，列数为qm(m=i,i+1,…,j)且相邻矩阵是可乘的(即qm=pm+1)。设它们的最佳计算次序所对应的乘法次数为m[i][j]，则AiAi+1…Ak的最佳计算次序对应的乘法次数为m[i][k]，Ak+1Ak+2…Aj的最佳计算次序对应的乘法次数为m[k+1][j]。 当i=j时，只有一个矩阵,故m[i][i]=0； 当ij时，将n个矩阵的行数和列数存储在数组P[0:n],则上述递归式可改写为： 算法设计 步骤1：确定合适的数据结构。采用数组m来存放各个子问题的最优值，数组s来存放各个子问题的最优决策; 步骤2：初始化。令m[i][i]=0，s[i][i]＝0，其中i=1,2,…,n； 步骤3：循环阶段。 步骤3-1：按照递归关系式计算2个矩阵AiAi+1相乘时的最优值并将其存入m[i][i+1]，同时将最优决策记入s[i][i+1]，i=1,2,…,n-1； 步骤3-2：按照递归关系式计算3个矩阵AiAi+1Ai+2相乘时的最优值并将其存入m[i][i+2]，同时将最优决策记入s[i][i+2]，i=1,2,…,n-2； 依此类推，直到…… 步骤3-(n-1)：按照递归关系式计算n个矩阵A1A2…An相乘时的最优值并将其存入m[1][n]，同时将最优决策记入s[1][n]。 至此，m[1][n]即为原问题的最优值。 步骤4：根据数组s记录的最优决策信息来构造最优解。 步骤4-1：递归构造A1…As[1][n]的最优解，直到包含一个矩阵结束； 步骤4-2：递归构造As[1][n]+1…An的最优解，直到包含一个矩阵结束； 步骤4