动态规划应用

1、动态规划算法的应用一、动态规划的概念近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态 规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推 和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一 个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则 称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而 就有许多策略供我们选

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

3、C,而第四个阶段是点C到点D。状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称 为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前 一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段 是三个状态C1, C2和C3,而第四个阶段又是一个状态D。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了 方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但 从分析的观点，有时将状态作为连续的处理将会有很大的好

4、处。此外，状态可以有多个分量（多维情形）， 因而用向量来代表；而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变 量取值的集合称为状态集合。无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的 发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程 的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些 点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线 路（所通过的点）的影响。状态的这个性

5、质意味着过程的历史只能通过当前的状态去影响它的未来的 发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决 策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同 的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决 策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的 策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优

6、策略。给定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也是B1到D的最短路径.事实正是如此，因此我们认为这个例子满足最优性原理的要求。 0C20C2是A到C2的最短路径，B

7、10B10D,这些点的选择构成了这个例子的最优策略，根据最优性 原理，这个策略的每个子策略应是最优：A0C20B10最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D,我们知道，最短路 径是A动态规划练习题USACO 2.2 Subset Sums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N = 3,对于1, 2, 3能划分成两个子集合，他们每个的所有数字和是相等的： and 1,2这是唯一一种分发(交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数)如果N = 7

8、,有四种方法能划分集合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 INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出0。

9、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 (s % 4) fout 0 endl;fout.close ();return ;s /= 4;int i, j;

10、dyn 0 = 1;for (i = 1; i = i; j-)dynj += dynj-i;fout (dyns/2) endl;fout.close();return 0;USACO 2.3 Longest Prefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序 列分解成较短的(称之为元素的)序列很感兴趣。如果一个集合P中的元素可以通过串联(允许重复；串联，相当于Pascal中的+”运算符) 组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。 举个例子，序列ABABACABAAB可以分解为下面集合中的元素

11、：A, AB, BA, CA, BBC序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个元素集合以及一 个大写字母序列，计算这个序列最长的前缀的长度。PROGRAM NAME: prefixINPUT FORMAT输入数据的开头包括1.200个元素(长度为1.10)组成的集合，用连续的以空格分开的字 符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个.的行。 集合中的元素没有重复。接着是大写字母序列S，长度为1.200,000，用一行或者多行的字符串 来表示，每行不超过76个字符。换行符并不是序列S的一部分。SAMPLE INPUT (file pr

12、efix.in)A AB BA CA BBCABABACABAABCOUTPUT FORMAT只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。SAMPLE OUTPUT (file prefix.out) 11示例程序如下：#include #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, lv

13、2, lv3;if (fin = fopen(prim.in, r) = NULL)perror (fopen fin);exit(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 = 1

14、;best = 0;for (Iv = 0; Iv 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”, best);return 0;USACO 3.1 Score Inflation题目如下：我们试着设计

15、我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。我们可以从几个种类中选取竞赛的题目，这里的一个”种类”是指一个竞赛题目的集合，解决集合中 的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目 的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1 = M = 10,000)和N,种类”的数目1 = N = 10,000。后面的每一行将包括两个整数来描述一个”种类”：第一个整数说明解决这种题目能得的分数(1 = points = 10000),第二整数说明解决这种题 目所需的时间(1 = minute

16、s = 10000)。你的程序应该确定我们应该从每个”种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。来自任意的”种类”的题目数目可能任何非负数(0或更多)。计算可能得到的最大分数。PROGRAM NAME: inflateINPUT FORMAT第1行：M, N-竞赛的时间和题目”种类”的数目。第2-N + 1行：两个整数:每个”种类”题目的分数和耗时。SAMPLE INPUT (file inflate.in)300 4100 60250 120120 10035 20OUTPUT FORMAT单独的一行包括那个在给定的限制里可能得到的最大的分数。SAMPLE OUTPUT (fi

17、le inflate.out)605从第2个”种类”中选两题，第4个种类”中选三题示例程序如下：#include ifstream fin(inflate.in);ofstream fout(inflate.out);const short maxm = 10010;long bestmaxm, m, n;voidmain()short i, j, len, pts;fin m n;for (j = 0; j = m; j+)bestj = 0;for (i = 0; i pts len;for (j = len; j bestj)bestj = bestj-len + pts;fout be

18、stm endl; /由于数组元素不减，末元素最大USACO 3.3 A Game题目如下：有如下一个双人游戏:N(2 = N = 100)个正整数的序列放在一个游戏平台上，两人轮流从序 列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分 多者为胜。编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。 你的程序要始终为第二位玩家执行最优策略。PROGRAM NAME: game1INPUT FORMAT第一行：正整数N,表示序列中正整数的个数。第二行至末尾：用空格分隔的N个正整数(大小为1-200)。SAMPLE INPU

19、T (file game1.in)64 7 2 95 2OUTPUT FORMAT只有一行，用空格分隔的两个整数：依次为玩家一和玩家二最终的得分。SAMPLE OUTPUT (file gamel.out)18 11参考程序如下：#include #define NMAX 101int bestNMAX2, tNMAX;int n;voidreadx () int i, aux;freopen (game1.in”, r, stdin);scanf (%d”, &n);for (i = 1; i y ? y : x;voidsolve () int i, l;for (l = 1; l = n

20、; l+)for (i = 1; i + l = n + 1; i+)bestl%2 = ti + l - 1 - ti - 1 - min (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);intmain () readx ();solve ();writex ();return 0;USACO 3.4 Raucous Rockers题目如下：你刚刚得

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

22、rs.in) 4 5 2 4 3 4 2OUTPUT FORMAT一个整数，表示可以装进M张CD盘的乐曲的最大数目。SAMPLE OUTPUT (file rockers.out) 3参考程序如下：#include #define MAX 25 int dpMAXMAXMAX, lengthMAX; int main () 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,

23、&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 = numsongs; c+) for (d = c + 1; d = numsongs; d+) if (b + lengthd dpab + lengthdd) dpab + lengthdd = dpac + 1;else if (dpac + 1 dpa +

24、 1lengthdd)dpa + 1lengthdd = dpac + 1;if (dpac best)best = dpac;fprintf (out, %dn”, best);return 0;解决背包问题动态规划的定义：动态规划的基本思想是把待求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的 解得到原问题的解，其中用动态规划分解得到的子问题往往不是互相独立的。动态规划在查找有很多 重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它 们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时 的结果，因而不

25、会在解决同样的问题时花费时间。动态规划只能应用于有最优子结构的问题。最优子 结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一 定的近似)。简单地说，问题能够分解成子问题来解决。求解步骤如下：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。问题描述及实现：背包问题：解决背包问题的方法有多种，动态规划，贪心算法，回溯法，分支定界法都能解决背包问 题。其中动态规划，回溯法，分支定界法都是解决0-1背包问题的方法。背包问题与0-1背包问题的 不同点在于在选择物品装入背包时，可以只选择物

26、品的一部分，而不一定是选择物品的全部。在这里， 我们组用的有贪心法和动态规划法来对这个问题进行算法的分析设计。用动态规划的方法可以看出如 果通过第n次选择得到的是一个最优解的话，那么第n-1次选择的结果一定也是一个最优解。这符合 动态规划中最优子问题的性质。动态规划方法是处理分段过程最优化一类问题极其有效的方法。在实 际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状 态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。考 虑用动态规划的方法来解决，这里的：阶段是：在前n件物品中，选取若干件物品放入背包中；状态是：在前n件

27、物品中，选取若干件物品放入所剩空间为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 ,i0, j=wi;f(i,j) = f(i-1,j) , i0, j=w0;f(0,j) = 0, i=0, jw0;代码实现：package zyf;public class bagPro public static void main(String args) / TODO自动生成方法存根int w = 2,2,6,5,4; /5个物体各自的重量int v = 6,3,5,4,6; /5个物体各自的价值int c = 10; /最