动态规划经典题目及解答整理.pdf

发布时间：2022-06-15 发布人：admin 分类：说明书资料大小：0.38M 资料格式：pdf 举报版权申诉

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第1页.png

第1页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第2页.png

第2页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第3页.png

第3页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第4页.png

第4页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第5页.png

第5页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第6页.png

第6页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第7页.png

第7页 / 共8页

5b76bb14-eaef-4b38-bc0b-ee53b1f16c29.pdf-第8页.png

第8页 / 共8页

动态规划经典题目及解答整理

1．最长公共子序列

a) 最长公共子序列的结构

c) 计算最优值

2．计算矩阵连乘积

3．凸多边形的最优三角剖分

4．防卫导弹

5．石子合并

6．最小代价子母树

7．商店购物

8．旅游预算

9．皇宫看守

10．游戏室问题

12.*田忌赛马

动态规划经典题目及解答整理标签： ACM 1．最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=，则另一序列Z=是X的子序列是指存在一个严格递增的下标序列，使得对于所有j=1,2,…,k有解答如下： a) 最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列X=和Y=的一个最长公共子序列Z=，则： i. 若xm=yn，则zk=xm=yn且Zk1是Xm1和Yn1的最长公共子序列； ii. 若xm≠yn且zk≠xm ，则Z是Xm1和Y的最长公共子序列； iii. 若xm≠yn且zk≠yn ，则Z是X和Yn1的最长公共子序列。其中Xm1=，Yn1=，Zk1=。最长公共子序列问题具有最优子结构性质。 b) 子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当 xm=yn时，找出Xm1和Yn1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm1和Y的一个最长公共子序列及X和Yn1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn1及Xm1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm1和Yn1的最长公共子序列。我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或 j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下： c) 计算最优值由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m ,0..n] 和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。程序如下：

#include #include int lcs_length(char x[], char y[]); int main() { char x[100],y[100]; int len; while(1) { scanf("%s%s",x,y); if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束 break; len=lcs_length(x,y); printf("%d\n",len); } } int lcs_length(char x[], char y[] ) { int m,n,i,j,l[100][100]; m=strlen(x); n=strlen(y); for(i=0;il[i‐1][j]) l[i][j]=l[i][j‐1]; else l[i][j]=l[i‐1][j]; return l[m][n]; } 由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。思考：空间能节约吗？ 2．计算矩阵连乘积在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：现在的问题是，给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n1。要求计算出这n个矩阵的连乘积 A1A2…An。递归公式：程序如下：

#include int main() { int p[101],i,j,k,r,t,n; int m[101][101]; //为了跟讲解时保持一致数组从1开始 int s[101][101]; //记录从第i到第j个矩阵连乘的断开位置 scanf("%d",&n); for(i=0;i<=n;i++) scanf("%d",&p[i]); //读入p[i]的值(注意：p[0]到p[n]共n+1项) for(i=1;i<=n;i++) //初始化m[i][i]=0 m[i][i]=0; for(r=1;r

4．防卫导弹一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： a)它是该次测试中第一个被防卫导弹截击的导弹； b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度。输出数据：截击导弹的最大数目。分析：定义l[i]为选择截击第i个导弹，从这个导弹开始最多能截击的导弹数目。由于选择了第i枚导弹，所以下一个要截击的导弹j的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个 j，满足h[j]<=h[i]的j中l[j]的最大值。程序如下： #include int main() { int i,j,n,max,h[100],l[100]; scanf("%d",&n); for(i=0;i=0;i‐‐) { max=0; for(j=i+1;jh[j]&&max

Sample Input 4 4 5 9 4 Sample Output －4 5 9 －4 －8 －5 9 －13 －9 22 4 －5 －9 4 4 －14 －4 －4 －18 22 6．最小代价子母树设有一排数，共n个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。输入、输出数据格式与“石子合并”相同。 Sample Input 4 12 5 16 4 Sample Output －12 －5 16 4 17 －16 －4 －17 －20 37 7．商店购物某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU因为： 1朵花加2个花瓶优惠价：10 ICU 2朵花正常价：4 ICU 输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。两个文件中都只用整数。第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3 个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数， 1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。输出数据：在输出文件OUTPUT．TXT中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。

8．旅游预算一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1 元=100分）。编写程序估计实际行驶在某路线所需的最小费用。输入数据：从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况：第一行为起点到终点的距离（实数）第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。输出数据：答案输出到当前目录下的文本文件“route.out”中。该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。 Sample Input 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 Sample Output 38.09 1 2 9．皇宫看守太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。输入数据：输入数据由文件名为intput.txt的文本文件提供。输入文件中数据表示一棵树，描述如下：第1行 n，表示树中结点的数目。第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0

25 10．游戏室问题有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于等于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到多少的快乐。 11． *基因问题已知两个基因序列如s：AGTAGT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出： A G C T 〕 A 5 2 1 2 4 G 2 5 4 3 2 C 1 4 5 5 1 T 2 3 5 5 2 〕 4 2 1 2 提示：定义问题l[i][j]为取第一个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值与三个子问题有关，l[i1][j1]、l[i][j1]、l[i1][j]。建立递归公式如下：其中m[0][t[j]表示表中空格和t[j]匹配的对应值。思考：本问题的初始化。 12.*田忌赛马田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：若田忌的马快，就让这两匹马比赛；若田忌的马慢，干脆就让他对付齐王最快的马；若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。则：程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1 匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。程序如下：

#include void readdata(); void init(); int n,a[100],b[100],l[100][100]; int main() { int i,j; readdata(); init(); for(i=n‐2;i>=0;i‐‐) for(j=1;jb[j]) l[i][j]=l[i+1][j‐1]‐1; else if(l[i+1][j‐1]‐1>l[i][j‐1]) l[i][j]=l[i+1][j‐1]‐1; else l[i][j]=l[i][j‐1]; printf("%d",l[0][n‐1]); } void readdata() { int i; scanf("%d",&n); for(i=0;i

分享到：

赞收藏

资料库

动态规划经典题目及解答整理.pdf

相关推荐

后端

热门标签

最新资料