实验三动态规划算法实验.doc

《实验三动态规划算法实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三动态规划算法的应用一、实验目的1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。2．熟练掌握分阶段的和递推的最优子结构分析方法。3．学会利用动态规划算法解决实际问题。二、实验内容1.问题描述：题目一：数塔问题给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。输入样例（数塔）：9121510682189519710416输出样例（最大路径和）：59题目二：最长单调递增子序列问题设计

2、一个O（n2）复杂度的算法，找出由n个数组成的序列的最长单调递增子序列。题目三：CommonSubsequenceAsubsequenceofagivensequenceisthegivensequencewithsomeelements(possiblenone)leftout.GivenasequenceX=anothersequenceZ=isasubsequenceofXifthereexistsastrictlyincreasingsequence

3、i2,...,ik>ofindicesofXsuchthatforallj=1,2,...,k,xij=zj.Forexample,Z=isasubsequenceofX=withindexsequence<1,2,4,6>.GiventwosequencesXandYtheproblemistofindthelengthofthemaximum-lengthcommonsubsequenceofXandY.Theprograminputisfromatextfile.Each

4、datasetinthefilecontainstwostringsrepresentingthegivensequences.Thesequencesareseparatedbyanynumberofwhitespaces.Theinputdataarecorrect.Foreachsetofdatatheprogramprintsonthestandardoutputthelengthofthemaximum-lengthcommonsubsequencefromthebeginningofaseparateline

5、.输入样例abcfbcabfcabprogrammingcontestabcdmnp输出样例420题目四0-1背包问题给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。输入样例：2015311799510710

6、5输出样例192.数据输入：个人设定，由键盘输入。3.要求：1）上述题目任选一做。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。附：实验报告的主要内容一．实验目的二．问题描述三．算法设计包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等四.程序调试及运行结果分析五.实验总结附录：程序清单（程序过长，可附主要部分）