实验五动态规划问题算法设计

宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：5实验项目名称：动态规划问题算法设计学号姓名专业、班实验地点指导教师惠云时间一、实验目的及要求（1）掌握使用动态规划方法设计最优值问题的方法；（2）能够使用动态规划算法设计策略设计矩阵连乘和最长公共子序列问题的算法；（3）掌握0-1背包问题的算法设计方法。二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、VC++6.0编程环境。2、实验要求：(1)独立完成实验，源代码书写规范；(2)程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3)实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤1、设计求解n个矩阵连乘的最优计算次序问题的程序，并将在最优计算次序下所需的乘法次数及最优计算次序在屏幕上显示。n个矩阵的维数从键盘输入。2、设计求解x和y两个序列的最长公共子序列问题的程序，并将最长公共子序列的长度及最长公共子序列在屏幕上显示。x和y序列从键盘输入。3、设计求解0-1背包问题的程序，并将装入背包的物品的最大价值及最优装入序列在屏幕上显示。背包的最大容量，物品的重量、价值从键盘输入。四、实验结果与数据处理五、分析与讨论1、比较备忘录方法和动态规划方法求矩阵连乘问题的特点。2.分析求最长公共子序列长度和构造最长公共子序列两种算法的时间复杂度。六、教师评语签名：日期：年月日成绩