动态程序设计专题

1、动态程序设计是一种重要的算法动态程序设计是一种重要的算法设计技术。使用这种技术设计算法，设计技术。使用这种技术设计算法，能够高效地解决一类最优化问题。通能够高效地解决一类最优化问题。通常情况下，使用通常的递归策略求解常情况下，使用通常的递归策略求解这类最优化问题的时间复杂度是指数这类最优化问题的时间复杂度是指数级的，而使用动态程序设计方法解决级的，而使用动态程序设计方法解决它们的复杂度往往是多项式级的。那它们的复杂度往往是多项式级的。那么到底什么是动态规划，它能解决哪么到底什么是动态规划，它能解决哪类最优化问题，它为什么有这么高的类最优化问题，它为什么有这么高的效率，如何实现它呢？效率，如何实

2、现它呢？一、什么是动态程序设计一、什么是动态程序设计动态程序设计方法是一个多阶段最优化决策的过程。在现实生活中有一类特殊的活动，可将它的全过程分成若干个互相联系的阶段，在每一阶段都需要根据当前的状态做出决策，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，目的是要使整个过程达到最佳的效果。这就是多阶段最优化决策过程。在多阶段决策问题中，各个阶段采取的决策，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。二、简单的动态规划二、简单的动态规划例1、数字

3、三角形如图所示的一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走。1三角形行数100，三角形中的数字为整数0，1，99。输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30分析 根据给定的输入，我们考虑数据的存放采用二维数组，从中间的任意一点ai,j分析，到达该点的路径最大值取决于ai-1,j-1和ai-1,j两者的最大值，即 ai,j=ai,j+max(

4、ai-1,j-1,ai-1,j)，对于初始值（起点）a1,1已知，该题可解。对例改变走向例2、更改上题条件每一步可以向下或向右走，我们分析对于任意一点ai,j来说，到达该点的路径最大值ai,j=ai,j+max(ai-,k)(1=k=j)。例3、导弹拦截某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹数量N(1N1000)和导弹依次飞来的高度hi(雷达给出的高度不大于300

5、00的正整数)。计算这套系统最多能拦截多少导弹，并依次打印输出被拦截导弹的高度。分析：对于序列中任意一枚导弹i，假设它是一个可行序列中的最后一枚导弹，那么这个可行序列是前面到i这些枚导弹中满足高度小于这枚导弹的高度的最长序列。设ai为每个导弹的高度，fi为以ai高度为序列中最后一枚导弹的最长序列，则fi=max(fk+1)1=k=i-1,满足akai例4：合唱队形【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，则他们的身高满

6、足T1 T2 Ti+1 TK (1 = i = K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件chorus.in的第一行是一个整数N（2 = N = 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 = Ti = 230）是第i位同学的身高（厘米）。【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8186 186 150 200 160 130 197 220【样例输出】4【数据规模】对于50%的数据，保证有n = 20；对于全部

7、的数据，保证有n = 100。分析：对于每个人来说，假设他是队伍中最高的，分析：对于每个人来说，假设他是队伍中最高的，求出他前面的最长上升序列个数求出他前面的最长上升序列个数ai，求出他后面，求出他后面下降序列序列的最长个数下降序列序列的最长个数bi，从而求出他作为队，从而求出他作为队伍最高应出队人数伍最高应出队人数n-ai-bi+1，这样找出，这样找出n个人个人的最小值问题解决的最小值问题解决三、背包问题三、背包问题在动态程序设计中，有一类问题看起来搜索策略可以完成，但分析数据规模，搜索难以承受。仔细分析对于每一个涉及到的个体，要么被取，要么不取，要么可以重复取多次，而对于达到的状态，存在从

8、这些状况中的最优解。即属于背包问题例、例1、有一个箱子容量为v(正整数，ov20000)，同时有n个物品(on30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 样例输入：24 一个整数，表示箱子容量6 一个整数，表示有n个物品8 接下来n行，分别表示这n个物品的各自体积。312797输出： 0一个整数，表示箱子剩余空间。例2：改变上题条件，每个物品有足够多（即可重复性背包问题）已知道空的猪猪背囊的重量空的猪猪背囊的重量E和装满金币的背囊的重量装满金币的背囊的重量F。还知道一共有一共有N种金币种金币，其中第第i种金币的面值为种金币的面值为

9、Pi，重量为，重量为Wi。知道了这些数据，请计算出猪猪背囊里的金币至少是多少钱。输入：输入：输入文件第一行为两个正整数E,F(1=E=F=1000)，E为空的猪猪背囊的重量，F为装满金币的猪猪背囊的重量。第二行为一个正整数N(1=N=50)，表示金币的种类。接下来的N行，每行包含两个整数，第i+2行的两个数Pi和Wi分别表示第i种金币的面值和重量，1=Pi=60，1=Wi=100。输出：输出： 输出文件仅一行，如果所要求的最少钱数存在，则输出一个整数，为钱数X。否则，输出一行This is impossible. 。 样例输入：样例输入：pocket.in10 11021 130 50样例输出

10、：样例输出：pocket.out60 四、动态规划的深入探讨例1、 问题问题C:K好数（好数（K-Good Number）问题描述：问题描述：如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。输入格式：输入格式：从文件读入数据，第一行为K、，其中K=16，L=10。输出格式：输出格式：将结果输出到 KGOOD.OUT 输入：4 2输出：7样例解释：11 13 20 22 30 31 33分析分析：设fx,d为x位最后一位为数字d的k好数的个数，转移方程fx,d=sum(fx-1,j)(0=j=k-1且j与d不相邻)例2、乘积最大设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法：1）3*12=362