实验报告2 动态规划

1、算法设计与分析实验报告实验名称动态规划学 院数学与计算机学院班级信科00000学号 6666666666姓 名 0000002016 年姓名实验日期实验名称动态规划【实验目的】理解动态规划算法的思想，能灵活利用动态规划算法解决实际计算问题。【实验内容】参考源码 MatrixChain.cpp,RecurveMatrixChain.cpp,lookupMatrixChain.cpp阅读参考代码，理解动态规划算法的主要数据结构；比较动态规划算法和分治算法的异同；比较规划算法和备注算法的异同；针对4.6, 4.7两节问题，在巳有动态规划算法基础上，编程求解最优解;【实验原理】（含相关算法流程图，可写

2、多页）【实验环境】微型计算机；Windows7操作系统；Code blocks、vs2012 集成开发环境。【实验过程与结果】（附主要源码及运行结果截图）最长单调子序列问题#include #define MAXLENGTH 1000using namespace std;int LongestIncreasingSubsequence（int X, int n, int c, int line）（int pathMAXLENGTH;gEi岫=i;c0 = 1；输入数组5= 1；in；+i，ci = 1;for (int j = 0; j = Xj & cj + 1 ci)ci = cj +

3、1;蛔=int max = 0;int end = -1;得到最大和获得最长递增子序列的最后一个元素的索引int cMAXLENGTH;int lineMAXLENGTH;while (cin n, n != 0)(for (int i = 0; i Xi;int max = LongestIncreasingSubsequence(X, n, c, line);cout Longest Increasing Subsequences Length: max = 0; -i)(cout linei;cout endl;:/打印res数组for (int i = 1; i = n; i+) (f

4、or (int j = 1; j = i; j+) (，;广5cout endl;*/cout res11 endl;/最 大路径和值/找出靠右路径int y = 1;cout arr1y ;/顶部最大for (int i = 2; i = n; i+) (/从上往下找，只需要比较y和y+1,相应输出“最大值下标对应的”原值if (resiy = resiy+1) cout arriy+1 : y = y+1;/更新 yelse ifcout endl;return 0; IXWpprQliMgtolMPebiWViCM 6 4 5re.imMl Q (QiO) 皿昌皿访皿 tijw : 89

5、. 457 s te-F? snv key to -critLrv.H-快拘械吾滴A注全:2I41&【实验小结】分治法与动态规划主要共同点：二者都要求原问题具有最优子结构性质，都是将原问题分而治之,分解成若十个规模较 小（小到很容易解决的程序）的子问题.然后将子问题的解合并，形成原问题的解.分治法与动态规划实现方法：分治法通常利用递归求解.动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下 求解.分治法与动态规划主要区别：分治法将分解后的子问题看成相互独立的.动态规划将分解后的子问题理解为相互间有联系，有重叠部分.2.相同点解决的问题都需要最优子结构备忘录方法与动态规划和递归的区别：1、动态规划是自低向上，备忘录方法是自顶向下，递归是自顶向下2、动态