实验三动态规划.docx

实验三动态规划 算法 分析 与 设计 实验报告 学号 姓名 班级 上课地点 教师 上课时间 实验 三 动态规划 1. 实验目的 1.1 理解动态规划算法的主要设计思想和基本步骤； 1.2 掌握用动态规划策略解决实际问题。 2. 实验环境 2.1 Eclipse 2.2 Window XP 3. 实验内容 3.1 矩阵连乘问题 3.2 最长公共子序列问题 3.3 0-1 背包问题 4. 教师批改意见 签字： 日期： 成绩 实验报告细表 1 1. . 矩阵连乘问题 1.1 算法设计思想 (1) 分析最优解：计算 Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的 (2)建立递归关系：设计算 Ai:j，1ijn，所需要的最少数乘次数 mi,j，则原问题的最优值为 m1,n 当 i=j 时，Ai:j=Ai，因此，mi,i=0，i