动态规划讲解大全含例题及答案

1、动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process) 最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程 (mWtistepdecision process)的优化问题时,提出了著名的最优化原理 (principle of optimality) ,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法一一动态规划.1957年出版了他的名著 Dynamic Programming ,这是该领域的第一本著作.动态规划问世以来,在经济治理、生产调度

2、、工程技术和最优限制等方面得到了广泛的应用.例 如最短路线、库存治理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求 解更为方便.虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态 规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动 态规划方法方便地求解.动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法.不象前面所 述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清楚的解题方法.动态规划程序设 计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不

3、相同,因而动态 规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解 决各类最优化问题.因此读者在学习时,除了要对根本概念和方法正确理解外,必须具体问题具体分 析处理,以丰富的想象力去建立模型,用创造性的技巧去求解.我们也可以通过对假设干有代表性的 问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法.根本模型多阶段决策过程的最优化问题.在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成假设干个互相联系的阶段, 在它的每一阶段都需要作出决策,从而使整个过程到达最好的活动效果.当然,各个阶段决策的选取 不是任意确定的,它依赖于当前面临的状态,

4、又影响以后的开展,当各个阶段决策确定后,就组成一 个决策序列,因而也就确定了整个过程的一条活动路线,如下列图：看词条图这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问 题就称为多阶段决策问题.记忆化搜索给你一个数字三角形,形式如下：12 34 5 67 8 9 10找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.无论对与新手还是老手,这都是再熟悉不过的题了,很容易地,我们写出状态转移方程：f(i, j)=ai, j + minf(i+1, j) , f(i+1, j + 1)对于动态规划算法解决这个问题,我们根据状态转移方程和状态转移方向,

5、比较容易地写出动态 规划的循环表示方法.但是,当状态和转移非常复杂的时候,也许写出循环式的动态规划就不是那么 简单了.解决方法:实用文档.我们尝试从正面的思路去分析问题,如上例,不难得出一个非常简单的递归过程：f1:=f(i-1,j+1); f2:=f(i-1,j);if f1>f2 then f:=f1+ai,j else f:=f2+ai,j;显而易见,这个算法就是最简单的搜索算法.时间复杂度为 2n,明显是会超时的.分析一下搜索 的过程,实际上,很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次.为了预防浪 费,很显然,我们存放一个opt数组：Opti, j-每产生一个f

6、(i, j),将f(i, j)的值放入opt中,以后再次调用到f(i, j)的时候,直接从opti, j来取就可以了.于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度, 预防了动态规划状态转移先后的问题,而且在相当多的情况下,递归算法能更好地预防浪费,在比赛 中是非常实用的.状态决策决策：当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁.而以前状态也就决定了 当前状态的情况.数字三角形的决策就是选择相邻的两个以前状态的最优值.状态：我们一般在动规的时候所用到的一些数组,也就是用来存储每个状态的最优值的.我们就从

7、动态规划的要诀,也就是核心局部“状态开始,来逐步了解动态规划.有时候当前状态确定后,以前状态就已经确定,那么无需枚举.动态规划算法的应用一、动态规划的概念近年来,涉及动态规划的各种竞赛题越来越多,每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高,已经不再停留于简单的递推 和建模上了.要了解动态规划的概念,首先要知道什么是多阶段决策问题.1 .多阶段决策问题如果一类活动过程可以分为假设干个互相联系的阶段,在每一个阶段都需作出决策采取举措,一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线, 那么称它为多

8、阶段决策问题.各个阶段的决策构成一个决策序列,称为一个策略.每一个阶段都有假设干个决策可供选择,因 而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定.策 略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使 在预定的标准下到达最好的效果 2 .动态规划问题中的术语阶段：把所给求解问题的过程恰当地分成假设干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量.在多数情况下,阶段变量是离散的,用k表示.此外,也有阶段变量是连续的情形.如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间 允

9、许有无穷多个决策时,阶段变量就是连续的.在前面的例子中,第一个阶段就是点 A,而第二个阶段就是点 A到点B,第三个阶段是点B到点C, 而第四个阶段是点 C到点Do实用文档. 状态：状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不 可控因素.在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶 段某支路的终点.在前面的例子中,第一个阶段有一个状态即A,而第二个阶段有两个状态 B1和B2,第三个阶段是三个状态C1, C2和C3,而第四个阶段又是一个状态Do过程的状态通常可以用一个或一组数来描述,称为状态变量.一般,状态是离散的,但有时为了

10、 方便也将状态取成连续的.当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但 从分析的观点,有时将状态作为连续的处理将会有很大的好处.止匕外,状态可以有多个分量(多维情形),因而用向量来代表；而且在每个阶段的状态维数可以不同.当过程按所有可能不同的方式开展时,过程各段的状态变量将在某一确定的范围内取值.状态变 量取值的集合称为状态集合.无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态,那么在这一阶段以后过程 的开展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了.换句话说,过 程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路

11、的始点,确定了这 些点的序列,整个线路也就完全确定.从某一阶段以后的线路开始,当这段的始点给定时,不受以前 线路所通过的点的影响.状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来 的开展,这个性质称为无后效性.决策：一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择行动称为决 策.在最优限制中,也称为限制.在许多间题中,决策可以自然而然地表示为一个数或一组数.不同 的决策对应着不同的数值.描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决 策时只需考虑当前的状态而无须考虑过程的历史.决策变量的范围称为允许决策集合.策略：由每个阶段的决策组成的序列称为策

12、略.对于每一个实际的多阶段决策过程,可供选取的 策略有一定的范围限制,这个范围称为允许策略集合.允许策略集合中到达最优效果的策略称为最优 策略.给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看 成(x(k) , u(k)与x(k+1)确定的对应关系,用 x(k+1)=Tk(x(k),u(k) 表示.这是从k阶段到k+1阶段 的状态转移规律,称为状态转移方程.最优性原理：作为整个过程的最优策略,它满足：相对前面决策所形成的状态而言,余下的子策略

13、 必然构成“最优子策略.D也是B1到D的最短路径事实正是如此,因此我们认为这个例子满足最优性原理的要求.C2 C2是A到C2的最短路径,B1 B1 D,这些点的选择构成了这个例子的最优策略,根据最优性 原理,这个策略的每个子策略应是最优：A C2 B1最优性原理实际上是要求问题的最优策略的子策略也是最优.让我们通过对前面的例子再分析来具体说明这一点：从A到D,我们知道,最短路径是A动态规划练习题USACO 2.2 Subset Sums题目如下：对于从1到N的连续整集合合,能划分成两个子集合,且保证每个集合的数字和是相等的.举个例子,如果N=3,对于1, 2, 3能划分成两个子集合,他们每个的

14、所有数字和是相等的：and 1,2这是唯一一种分发交换集合位置被认为是同一种划分方案,因此不会增加划分方案总数如果N=7,有四种方法能划分集合1 , 2, 3, 4, 5, 6, 7,每一种分发的子集合各数字和是相等 的：1,6,7 and 2,3,4,5 注 1+6+7=2+3+4+52,5,7 and 1,3,4,63,4,7 and 1,2,5,61,2,4,7 and 3,5,6给出N,你的程序应该输出划分方案总数,如果不存在这样的划分方案,那么输出 0o程序不能预 存结果直接输出.PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行,且只有一个整数NSAM

15、PLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数,如果不存在那么输出0oSAMPLE OUTPUT (file subset.out)4参考程序如下：#include <fstream>using namespace std;const unsigned int MAX_SUM = 1024;int n;unsigned long long int dynMAX_SUM;ifstream fin ("subset.in");ofstream fout ("subset.out");int mai

16、n() fin >> n;fin.close();int s = n*(n+1);if (s % 4) fout << 0 << endl;fout.close ();return ;s /= 4;实用文档.int i, j;dyn 0 = 1;for (i = 1; i <= n; i+)for (j = s; j >= i; j-) dynj += dynj-i;fout << (dyns/2) << endl;fout.close();return 0; USACO 2.3 Longest Prefix题目如下：在生

17、物学中,一些生物的结构是用包含其要素的大写字母序列来表示的.生物学家对于把长的序 列分解成较短的称之为元素的序列很感兴趣.如果一个集合P中的元素可以通过串联允许重复；串联,相当于 Pascal中的“+运算符 组成一个序列S ,那么我们认为序列 S可以分解为P中的元素.并不是所有的元素都必须出现.举 个例子,序列ABABACABAAB!以分解为下面集合中的元素：A, AB, BA, CA, BBC序列S的前面K个字符称作S中长度为K的前缀.设计一个程序,输入一个元素集合以及一 个大写字母序列,计算这个序列最长的前缀的长度.PROGRAM NAME: prefixINPUT FORMAT输入数据的

18、开头包括1.200 个元素长度为1.10 组成的集合,用连续的以空格分开的字符 串表示.字母全部是大写,数据可能不止一行.元素集合结束的标志是一个只包含一个“.的行.集合中的元素没有重复.接着是大写字母序列S ,长度为1.200,000,用一行或者多行的字符串来表示,每行不超过76个字符.换行符并不是序列 S的一局部.SAMPLE INPUT (file prefix.in)A AB BA CA BBC .ABABACABAABCOUTPUT FORMAT只有一行,输出一个整数,表示 S能够分解成P中元素的最长前缀的长度.SAMPLE OUTPUT (file prefix.out) 11例如

19、程序如下：#include <stdio.h>#define MAXP 200#define MAXL 10char primMAXP+1MAXL+1;int nump;int start200001;char data200000;int ndata;int main(int argc, char *argv)(FILE *fout, *fin;int best;int lv, lv2, lv3;if (fin = fopen("prim.in", "r") = NULL)(perror ("fopen fin");ex

20、it(1);if (fout = fopen("prim.out", "w") = NULL)(perror ("fopen fout");exit(1);while (1)(fscanf (fin, "%s", primnump);if (primnump0 != '.') nump+;else break;ndata = 0;while (fscanf (fin, "%s", data+ndata) = 1)ndata += strlen(data+ndata);start0

21、 = 1;best = 0;for (lv = 0; lv < ndata; lv+) if (startlv)(best = lv;for (lv2 = 0; lv2 < nump; lv2+)(for (lv3 = 0; lv + lv3 < ndata && primlv2lv3 && primlv2lv3 = datalv+lv3; lv3+);if (!primlv2lv3)startlv + lv3 = 1;if (startndata) best = ndata;fprintf (fout, "%in", be

22、st);return 0;实用文档.USACO 3.1 Score Inflation题目如下：我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助.我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数.你的任务是写一个程序来告诉USACO勺职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大.输入包括竞赛的时间,M(1 <= M <= 10,000) 和N,"种类"的数目1 <= N <= 10,000 .

23、后面的每一行将包括两个整数来描述一个"种类":第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000).你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分 数.来自任意的"种类"的题目数目可能任何非负数(0或更多). 计算可能得到的最大分数.PROGRAM NAME: inflate INPUT FORMAT第1行：M, N-竞赛的时间和题目"种类的数目. 第2-

24、N+1行：两个整数：每个"种类"题目的分数和耗时.SAMPLE INPUT (file inflate.in) 300 4 100 60 250 120 120 100 35 20 OUTPUT FORMAT 单独的一行包括那个在给定的限制里可能得到的最大的分数.SAMPLE OUTPUT (file inflate.out) 605从第2个"种类中选两题,第4个"种类"中选三题 例如程序如下：#include <fstream.h> ifstream fin("inflate.in"); ofstream fo

25、ut("inflate.out"); const short maxm = 10010; long bestmaxm, m, n; void main() short i, j, len, pts;fin >> m >> n;for (j = 0; j <= m; j+)实用文档.bestj = 0;for (i = 0; i < n; i+) fin » pts » len;for (j = len; j <= m; j+) if (bestj-len + pts > bestj) bestj = bes

26、tj-len + pts;由于数组元素不减,末元素最大)fout « bestm « end I; /)USACO 3.3 A Game题目如下：有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上,两人轮流从序列的 两端取数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束.以最终得分多者 为胜.编一个执行最优策略的程序,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略.你的程序要始终为第二位玩家执行最优策略.PROGRAM NAME: gamelINPUT FORMAT第一行：正整数N,表示序列中正整数

27、的个数.第二行至末尾：用空格分隔的N个正整数大小为1-200.SAMPLE INPUT (file game1.in)64 7 2 95 2OUTPUT FORMAT只有一行,用空格分隔的两个整数：依次为玩家一和玩家二最终的得分.SAMPLE OUTPUT (file gamel.out)18 11参考程序如下：#include <stdio.h>#define NMAX 101int bestNMAX2, tNMAX;int n;voidreadx () int i, aux;freopen ("game1.in", "r", stdin)

28、;scanf ("%d", &n);for (i = 1; i <= n; i+) scanf ("%d", &aux);t = ti - 1 + aux;)fclose (stdin);)inline intmin (int x, int y) return x > y ? y : x;)voidsolve () int i, l;实用文档.for (l = 1; l <= n; l+)for (i = 1; i + l <= n + 1; i+)bestl%2 = ti + l - 1 - ti - 1 - m

29、in (besti + 1(l - 1) % 2, best(l - 1) % 2);)void writex () freopen ("game1.out", "w", stdout);printf ("%d %dn", best1n % 2, tn - best1n % 2); fclose (stdout);) int main () readx (); solve (); writex (); return 0;)实用文档.USACO 3.4 Raucous Rockers题目如下：你刚刚得到了流行的“破锣摇滚乐队录制的尚未发

30、表的N(1 <= N <= 20)首歌的版权.你打算从 中精选一些歌曲,发行 M(1 <= M <= 20)张CD每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐, 一首歌不能分装在两张 CD中.不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值.于是你决定根据以下标准进行选择： 歌曲必须根据创作的时间顺序在CD盘上出现.选中的歌曲数目尽可能地多.PROGRAM NAME: rockersINPUT FORMAT第一行：三个整数：N, T, M.第二行：N个整数,分别表示每首歌的长度,按创作时间顺序排列.SAMPLE INPUT (file

31、rockers.in) 4 5 2 4 3 4 2OUTPUT FORMAT一个整数,表示可以装进 M张CD盘的乐曲的最大数目.SAMPLE OUTPUT (file rockers.out) 3 参考程序如下：#include <stdio.h>#define MAX 25int dpMAXMAXMAX, lengthMAX;intmain () FILE *in = fopen ("rockers.in", "r"); FILE *out = fopen ("rockers.out", "w");

32、int a, b, c, d, best, numsongs, cdlength, numcds; fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds); for (a = 1; a <= numsongs; a+) fscanf (in, "%d", &lengtha);best = 0;for (a = 0; a < numcds; a+)for (b = 0; b <= cdlength; b+)for (c = 0; c <= numson

33、gs; c+) for (d = c + 1; d <= numsongs; d+) if (b + lengthd <= cdlength) if (dpac + 1 > dpab + lengthdd)dpab + lengthdd = dpac + 1;else 实用文档. if (dpac + 1 > dpa + 1lengthdd) dpa + 1lengthdd = dpac + 1;)if (dpac > best)best = dpac;)fprintf (out, "%dn", best);return 0;)实用文档.解决背

34、包问题动态规划的定义：动态规划的根本思想是把待求解的问题分解成假设干个子问题,先求解子问题,然后再从这些子问题 的解得到原问题的解,其中用动态规划分解得到的子问题往往不是互相独立的.动态规划在查找有很 多重叠子问题的情况的最优解时有效.它将问题重新组合成子问题.为了预防屡次解决这些子问题, 它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决.因此,动态规划保存递归 时的结果,因而不会在解决同样的问题时花费时间.动态规划只能应用于有最优子结构的问题.最优 子结构的意思是局部最优解能决定全局最优解对有些问题这个要求并不能完全满足,故有时需要引入一定的近似.简单地说,问题能够分解成子问

35、题来解决.求解步骤如下：1 .找出最优解的性质,并刻画其结构特征；2 .递归地定义最优值；3 .以自底向上的方式计算出最优值；4 .根据计算最优值时得到的信息,构造最优解.问题描述及实现：背包问题：解决背包问题的方法有多种,动态规划,贪心算法,回溯法,分支定界法都能解决背包问题.其中动态规划,回溯法,分支定界法都是解决0-1背包问题的方法.背包问题与0-1背包问题的不同点在于在选择物品装入背包时,可以只选择物品的一局部,而不一定是选择物品的全部.在这里, 我们组用的有贪心法和动态规划法来对这个问题进行算法的分析设计.用动态规划的方法可以看出如 果通过第n次选择得到的是一个最优解的话,那么第 n

36、-1次选择的结果一定也是一个最优解.这符合 动态规划中最优子问题的性质.动态规划方法是处理分段过程最优化一类问题极其有效的方法.在实 际生活中,有一类问题的活动过程可以分成假设干个阶段,而且在任一阶段后的行为依赖于该阶段的 状态,与该阶段之前的过程是如何到达这种状态的方式无关.这类问题的解决是多阶段的决策过程.考虑用动态规划的方法来解决,这里的：阶段是：在前n件物品中,选取假设干件物品放入背包中；状态是：在前n件物品中,选取假设干件物品放入所剩空间为w的背包中的所最大价值；决策是：第n件物品放或者不放；由此可以写出动态转移方程：我们用fi,j表示在前i件物品中选择假设干件放在所剩空间为j的背包里所能获得最大价值是：fi,j=maxfi-1,j-wi+pi (j>=wi), fi-1,j.这样,我们可以自底向上地得出在前m件物品中取出假设干件放进背包能获得的最大价值,也就是fm,w令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值f(i,j)=maxf(i-1,j), f(i-1, j-wi)+vi ,i>0, j>=wi;f(i,j) = f(i-1,j) , i>0, j<wi;f(0,j) = v0 , i=0, j>