1、动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision 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 f1f2 then f:=f1+ai,j else f:=f2+ai,j;显而易见，这个算法就是最简单的搜索算法。时间复杂度为 2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个 opt 数组：Opti, j - 每产生一个 f(i, j)，将 f(i, j)的值放
6、入 opt 中，以后再次调用到 f(i, j)的时候，直接从 opti, j来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.状态 决策决策：当前状态通过决策,回到了以前状态. 可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。状态：我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分
7、“状态” 开始，来逐步了解动态规划。有时候当前状态确定后 ,以前状态就已经确定,则无需枚举.动态规划算法的应用一、动态规划的概念近年来，涉及动态规划的各种竞赛题越来越多，每一年的 NOI 几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。1. 多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决
8、策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.2动态规划问题中的术语阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用 k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
9、在前面的例子中，第一个阶段就是点 A，而第二个阶段就是点 A 到点 B，第三个阶段是点 B 到点C，而第四个阶段是点 C 到点 D。状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即 A，而第二个阶段有两个状态 B1 和 B2，第三个阶段是三个状态 C1，C2 和 C3，而第四个阶段又是一个状态 D。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现
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 阶段的状态转移规律，称为状态转移方程。最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略 ”。D 也是 B
13、1 到 D 的最短路径 事实正是如此，因此我们认为这个例子满足最优性原理的要求。C2C2 是 A 到 C2 的最短路径，B1B1D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A C2B1 最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从 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，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出 0。程序不能预存结果直接输出。PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行，且只有一个整数 NSAMPLE I
15、NPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出 0。SAMPLE OUTPUT (file subset.out)4参考程序如下：#include 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 main() fin n;fin.close();int s = n*(n+1);if
16、 (s % 4) fout = i; j-)dynj += dynj-i;fout #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“);exit(1);if (fout = fo
17、pen(“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 = 1;best = 0;for (lv = 0; lv ifstream fin(“inflate.in“);ofstream fout(“inflate.o
18、ut“);const short maxm = 10010;long bestmaxm, m, n;voidmain()short i, j, len, pts;fin m n;for (j = 0; j pts len;for (j = len; j bestj)bestj = bestj-len + pts;fout #define NMAX 101int bestNMAX2, tNMAX;int n;voidreadx () int i, aux;freopen (“game1.in“, “r“, stdin);scanf (“%d“, for (i = 1; i y ? y : x;v
19、oidsolve () int i, l;for (l = 1; l #define MAX 25int dpMAXMAXMAX, lengthMAX;intmain ()FILE *in = fopen (“rockers.in“, “r“);FILE *out = fopen (“rockers.out“, “w“);int a, b, c, d, best, numsongs, cdlength, numcds;fscanf (in, “%d%d%d“, for (a = 1; a 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;解决背包问题动态规划的定义：动态规划的基本思想是把待求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解得到原问题的解，其中用动态规划分解得到的子问题往往不是互相独立的。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它
