《第六章 动态规划法--实验及练习》由会员分享，可在线阅读，更多相关《第六章 动态规划法--实验及练习（15页珍藏版）》请在金锄头文库上搜索。
1、我们毕业啦其实是答辩的标题地方算法设计与分析算法设计与分析第六章动态规划法实验1.实验题目编程实现图示多段图的最短路径问题的动态规划算法6.16.1实验项目实验项目多段图的最短路径问题多段图的最短路径问题 2实验目的（1）理解动态规划算法的概念；（2）掌握动态规划算法的基本要素；（3）掌握设计动态规划算法的步骤；（4）通过应用范例学习动态规划算法的设计技巧与策略。1.实验题目给定由n个整数组成的序列(a1,a2,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；3.实验要求（1）用动态规划法设计最大子段和
2、问题的算法；（2）比较用蛮力法、分治法和动态规划法解决此问题的时间性能；（3）给出测试数据，写出程序文档。6.26.2实验项目实验项目最大子段和问题最大子段和问题 1.实验题目给定由n个整数组成的序列(a1,a2,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；3.实验要求（1）用动态规划法设计最大子段和问题的算法；（2）比较用蛮力法、分治法和动态规划法解决此问题的时间性能；（3）给出测试数据，写出程序文档。6.26.2实验项目实验项目最大子段和问题最大子段和问题 6.36.3实验项目实验项目编辑距离编
3、辑距离【 问 题 描 述 】 编 辑 距 离 Levenshtein距 离 ， 由 俄 罗 斯 科 学 家VladimirLevenshtein在1965年提出。是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。给定两个字符串S和T，对于T我们允许三种操作：(1)在任意位置添加任意字符(2)删除存在的任意字符(3)修改任意字符问最少操作多少次可以把字符串T变成S？【输入】文件input.txt提供输入数据，第一行为字符串A，第二行为字符串B。【输出】文件output.txt为结果输出文件，第一行为编辑距离d（A，B）练习练习1 1： IsIs BiggerBigger Smarter?
4、Smarter? （越大越聪明？）（越大越聪明？）PC/UVaIDs:111101/10131,Popularity:B,Successrate:highLevel:2【问题描述】一些人认为，大象的体型越大，脑子越聪明。为了反驳这一错误观点，你想要分析一组大象的数据，找出尽量多的大象组成一个体重严格递增但IQ严格递减的序列。p【输入】：输入包含若干大象的数据，每行一头大象，直到输入结束。每头大象的数据包括两个整数：第一个是以千克为单位的体重，第二个是以整百为单位的IQ指数。两个整数均在1到10000之间。输入最多包含1000头大象。两头大象可能有相同的体重，或者相同的IQ，甚至体重和IQ都相同
5、。p【输出】：输出第一行应当包括一个整数n，为找到的大象序列的长度。接下来的n行，每行包含一个正整数，表示大象。用Wi和Si表示输入数据中第i行的两个数，则若找到的这一序列为a1，a2，.，an，则必须有：Wa1Wa2.Sa2.SaniSampleInput60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput44597p首先将所有大象按体重Wi升序排列，这样该问题就转化为了最长上升递减子序列LIS（LongestIncreasingSubsequence）问题。p定义状态d(i)，
6、代表前i个大象中以大象i作为序列结尾的最长上升子序列的长度。p状态转移方程：d(i)=maxd(k)+1|1=ki,WkSi练习练习2 2：10921092 回文字符串回文字符串回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。例如：abbc添加2个字符可以变为acbbca，也可以添加3个为abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。Input输入一个字符串Str，Str的长度=1000。Output输出最少添加多少个字符可以使之变为回文字串。Input示例AbbcOutput示例
7、2练习练习3 3：华为机试：华为机试 - -购物单（购物单（0-10-1背包背包+ +限制条件限制条件）p题目描述王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：p如果要买归类为附件的物品，必须先买该附件所属的主件。p每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。p王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使
8、每件物品的价格与重要度的乘积的总和最大。p设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk。（其中*为乘号）请你帮助王强设计一个满足要求的购物单。p输入描述:输入的第1行，为两个正整数，用一个空格隔开：Nm（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每 行 有 3个 非 负 整 数 v p q（ 其 中 v表 示 该 物 品 的 价 格（v0，表示该物品为附件，q是所属主件的编号）p输出描述:输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。国内OnlineJudge浙江工业大学http:/
