当前位置：文档视界 › 动态规划讲解大全(含例题及答案)

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

动态规划讲解大全

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

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

基本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。

记忆化搜索

给你一个数字三角形, 形式如下:

2 3

4 5 6

7 8 9 10

找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.

无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}

对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么

简单了。

解决方法：

我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程:

f1:=f(i-1,j+1); f2:=f(i-1,j);

if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];

显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.

状态决策

决策：

当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。

状态：

我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.

动态规划算法的应用

一、动态规划的概念

近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。

要了解动态规划的概念，首先要知道什么是多阶段决策问题。

1. 多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.

2．动态规划问题中的术语

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。

状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。

过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。

当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。

无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

决策变量的范围称为允许决策集合。

策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

给定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的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。?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}能划分成两个子集合，他们每个的所有数字和是相等的：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+5}

{2,5,7} and {1,3,4,6}

{3,4,7} and {1,2,5,6}

{1,2,4,7} and {3,5,6}

给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。

PROGRAM NAME: subset

INPUT FORMAT

输入文件只有一行，且只有一个整数N

SAMPLE INPUT (file subset.in)

OUTPUT FORMAT

输出划分方案总数，如果不存在则输出0。

SAMPLE OUTPUT (file subset.out)

参考程序如下：

#include

using namespace std;

const unsigned int MAX_SUM = 1024;

int n;

unsigned long long int dyn[MAX_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;

dyn [0] = 1;

for (i = 1; i <= n; i++)

for (j = s; j >= i; j--)

dyn[j] += dyn[j-i];

fout << (dyn[s]/2) << endl;

fout.close();

return 0;

}

USACO 2.3 Longest Prefix

题目如下：

在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。

如果一个集合P 中的元素可以通过串联（允许重复；串联，相当于Pascal 中的“+” 运算符）组成一个序列S ，那么我们认为序列S 可以分解为P 中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB 可以分解为下面集合中的元素：

{A, AB, BA, CA, BBC}

序列S 的前面K 个字符称作S 中长度为K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。

PROGRAM NAME: prefix

INPUT FORMAT

输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个“.” 的行。集合中的元素没有重复。接着是大写字母序列S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过76 个字符。换行符并不是序列S 的一部分。

SAMPLE INPUT (file prefix.in)

A A

B BA CA BBC

ABABACABAABC

OUTPUT FORMAT

只有一行，输出一个整数，表示S 能够分解成P 中元素的最长前缀的长度。

SAMPLE OUTPUT (file prefix.out)

示例程序如下：

#include

#define MAXP 200

#define MAXL 10

char prim[MAXP+1][MAXL+1];

int nump;

int start[200001];

char data[200000];

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 = fopen("prim.out", "w")) == NULL)

{

perror ("fopen fout");

exit(1);

}

while (1)

{

fscanf (fin, "%s", prim[nump]);

if (prim[nump][0] != '.') nump++;

else break;

}

ndata = 0;

while (fscanf (fin, "%s", data+ndata) == 1)

ndata += strlen(data+ndata);

start[0] = 1;

best = 0;

for (lv = 0; lv < ndata; lv++)

if (start[lv])

{

best = lv;

for (lv2 = 0; lv2 < nump; lv2++)

{

for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] && prim[lv2][lv3] == data[lv+lv3]; lv3++)

;

if (!prim[lv2][lv3])

start[lv + lv3] = 1;

}

if (start[ndata]) best = ndata;

fprintf (fout, "%i\n", best);

return 0;

}

USACO 3.1 Score Inflation

题目如下：

我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。

我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。

你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

输入包括竞赛的时间,M(1 <= M <= 10,000)和N,"种类"的数目1 <= N <= 10,000。

后面的每一行将包括两个整数来描述一个"种类":

第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。

你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的"种类"的题目数目可能任何非负数(0或更多)。

计算可能得到的最大分数。

PROGRAM NAME: inflate

INPUT FORMAT

第 1 行: M, N--竞赛的时间和题目"种类"的数目。

第2-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

ifstream fin("inflate.in");

ofstream fout("inflate.out");

const short maxm = 10010;

long best[maxm], m, n;

void

main()

{

short i, j, len, pts;

fin >> m >> n;

for (j = 0; j <= m; j++)

best[j] = 0;

for (i = 0; i < n; i++) {

fin >> pts >> len;

for (j = len; j <= m; j++)

if (best[j-len] + pts > best[j])

best[j] = best[j-len] + pts;

}

fout << best[m] << endl; // 由于数组元素不减，末元素最大

}

USACO 3.3 A Game

题目如下：

有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。

编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

PROGRAM NAME: game1

INPUT FORMAT

第一行: 正整数N, 表示序列中正整数的个数。

第二行至末尾: 用空格分隔的N个正整数（大小为1-200）。

SAMPLE INPUT (file game1.in)

4 7 2 9

5 2

OUTPUT FORMAT

只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。

SAMPLE OUTPUT (file game1.out)

18 11

参考程序如下：

#include

#define NMAX 101

int best[NMAX][2], t[NMAX];

int n;

void

readx () {

int i, aux;

freopen ("game1.in", "r", stdin);

scanf ("%d", &n);

for (i = 1; i <= n; i++) {

scanf ("%d", &aux);

t = t[i - 1] + aux;

}

fclose (stdin);

}

inline int

min (int x, int y) {

return x > y ? y : x;

}

void

solve () {

int i, l;

for (l = 1; l <= n; l++)

for (i = 1; i + l <= n + 1; i++)

best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],

best[(l - 1) % 2]);

}

void writex () {

freopen ("game1.out", "w", stdout);

printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);

fclose (stdout);

}

int

main () {

readx ();

solve ();

writex ();

return 0;

}

USACO 3.4 Raucous Rockers

题目如下：

你刚刚得到了流行的“破锣摇滚”乐队录制的尚未发表的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 rockers.in)

4 5 2

4 3 4 2

OUTPUT FORMAT

一个整数，表示可以装进M张CD盘的乐曲的最大数目。

SAMPLE OUTPUT (file rockers.out)

参考程序如下：

#include

#define MAX 25

int dp[MAX][MAX][MAX], length[MAX];

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", &numsongs, &cdlength, &numcds);

for (a = 1; a <= numsongs; a++)

fscanf (in, "%d", &length[a]);

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 + length[d] <= cdlength) {

if (dp[a][c] + 1 > dp[a][b + length[d]][d])

dp[a][b + length[d]][d] = dp[a][c] + 1;

}

else {

if (dp[a][c] + 1 > dp[a + 1][length[d]][d])

dp[a + 1][length[d]][d] = dp[a][c] + 1;

}

if (dp[a][c] > best)

best = dp[a][c];

}

fprintf (out, "%d\n", best);

return 0;

}

解决背包问题

动态规划的定义：

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

1. 找出最优解的性质，并刻画其结构特征；

2. 递归地定义最优值；

3. 以自底向上的方式计算出最优值；

4. 根据计算最优值时得到的信息，构造最优解。

问题描述及实现：

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

阶段是：在前n件物品中，选取若干件物品放入背包中；

状态是：在前n件物品中，选取若干件物品放入所剩空间为w的背包中的所最大价值；

决策是：第n件物品放或者不放；由此可以写出动态转移方程：

我们用f[i,j]表示在前i 件物品中选择若干件放在所剩空间为j 的背包里所能获得最大价值是：f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}。这样，我们可以自底向上地得出在前m件物品中取出若干件放进背包能获得的最大价值，也就是f[m,w]令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值

f(i,j)=max{f(i-1,j), f(i-1, j-w[i])+v[i] } ,i>0, j>=w[i];

f(i,j) = f(i-1,j) , i>0, j

f(0,j) = v[0] , i=0, j>=w[0];

f(0,j) = 0, i=0, j

代码实现：

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; //最大载重

int f[][] = new int [5][c+1]; //前i个物体装出重量为j的组合时的最大价值int maxValue = 0;

for(int j=0 ; j<=c; j++){

if(j>=w[0])

f[0][j] =v[0];

else

f[0][j] = 0;

}

for(int i=1; i

for(int j=0; j<=c;j++){

if(j

f[i][j] = f[i-1][j];

else if(f[i-1][j]>=f[i-1][j-w[i]]+v[i])

f[i][j] = f[i-1][j];

else

f[i][j] = f[i-1][j-w[i]]+v[i];

}

System.out.println(f[4][c]);

}

topcoder srm 442 d2 背包问题

n个正整数，可能有重复，现在要找出两个不相交的子集A和B，A和B不必覆盖所有元素，使A中元素的和SUM(A)与B中元素的和SUM(B)相等，且SUM(A)和SUM(B)尽可能大。

int MX = 500000;

int[,] c = new int[2,MX*2 + 1];

int T;

int function(int[] d)

{

int i,j;

for(i=0;i <= MX * 2;i++)

c[T,i] = -1;

c[T,MX] = 0;

for(i=0;i

T=1-T;

for(j=0;j

c[T,j] = c[1-T,j];

for(j=0;j

{

if(c[1-T,j] < 0)

continue;

c[T,j+d[i]] = Math.Max(c[T,j+d[i]],c[1-T,j]+d[i]);

c[T,j-d[i]] = Math.Max(c[T,j-d[i]],c[1-T,j]);

}

return c[T,MX] != 0 ? c[T,MX] : -1;

}

状态1是前i个元素，状态2是构造的两个子集的差的绝对值为j，保存的是较小的那个子集的最大sum。这样两个子集的和就分别是dp[i][j]和dp[i][j]+j。

然后枚举当前元素放在小集合还是大集合，或者干脆就不放。

设f[i][j]是考虑i个元素时A的和，j是A和B的差。

当考虑i+1时，有三种情况：

1. 跳过a[i+1],有f[i+1][j] = f[i][j];

2. 将a[i+1]加入A，有f[i+1][j+a[i+1]] = f[i][j] + a[i+1];

3. 将a[i+1]加入B，有f[i+1][j-a[i+1]] = f[i][j];

填完这个表格后，f[n][0]即为所求。

动态规划例题

例1：机器负荷分配问题某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表：时期(k) 1 2 3 4 需要量(d k ) 2（单位） 3 2 4 假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为：若 0＜x ≤6 ，则生产总成本＝3十1·x 若 x ＝0 ，则生产总成本＝0 又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元）年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年 0 1 23 21 6 8 19 22

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

动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。基本模型多阶段决策过程的最优化问题。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。记忆化搜索给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么

动态规划习题答案

2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配资金，使总效益值最大？## 表8－47 解：设S－A,B,C项目的总投资额，S－B、C项目的总投资额21S－C 项目的投资额；3X－k项目的投资额；k（X－A项目的投资额，X －B项目的投资额，X－C项目的投资额）312W（S,X）－对K项目投资X后的收益：W（S,X）＝W (X) kkkkkkkkk T (S,X)－S=S-X k k+1kkkk f (S)－当K至第3项目允许的投资额为S时所能获得的最大收益。kkk为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S＝0，建立递归方程4f(S)=0 k4

f (S)=max{ W (X)+f(S)} k=3,2,1 k+1kk +1kkk X∈D(S) kkk第一步，K=3 f(S)=0 44 f (S)=max{W (X)+f (S)} 434333X∈D(S) 333S=S-X3 34 第二步：)} f (S (X (S)=max{W)+f K=2 322322) X ∈D(S 222-X =S S232 W (X)+f (S-X) 22322

第三步：)} (S (X) =max f (S {W)+ f K=1 211121) D X∈(S111- X S= S 1 21 ) (X- X)+ f (SW1 12 11 S=4 →S=1 →S=1 312↓↓ ↓ X*=3 X*=0 X*=1 312百万。1投资C 不投资B 百万，3投资A．总收益164百万元。 3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？

动态规划习题

第七章动态规划规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。

动态规划练习试题和解答

动态规划练习题 [题1] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。输入格式：文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。输出格式：只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出: 对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0. 样例输入: 样例输出：

动态规划典型例题

1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4 输入第一行一个整数0

2、最长公共子序列描述如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。输入第一行给出一个整数N(0

3、括号匹配时间限制：1000 ms | 内存限制：65535 KB 描述给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的输入第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2

动态规划习题完整版

动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

动态规划专题分类视图数轴动规题：题1.2001年普及组第4题--装箱问题【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0

对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示 (A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60) 【输出】输出一行,为修好四件衣服所要的最短时间。【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不

动态规划法求解生产与存储问题

动态规划一·动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。二·动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=….n.表示。

1.状态状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。 n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。变量允许取值的范围称为允许决策集合（set of

经典的动态规划入门练习题

动态规划入门练习题 1.石子合并在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (1)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5 9 4 输出: －４５９－４－８－５９－１３－９２２４－５－９４４－１４－４－４－１８２２最小代价子母树设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小. 输入、输出数据格式与“石子合并”相同。输入样例： 4 12 5 16 4 输出样例：－１２－５１６４１７－１６－４－１７－２０３７

2.背包问题设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。输入数据：第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔；第二行N个数,为Ｎ种物品重量；两个数用空格分隔；第三行N个数,为N种物品价值; 两个数用空格分隔；输出数据：第一行总价值；以下N行，每行两个数，分别为选取物品的编号及数量；输入样例： 4 10 2 3 4 7 1 3 5 9 输出样例： 12 2 1 4 1 3.商店购物某商店中每种商品都有一个价格。例如，一朵花的价格是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中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）

动态规划习题精讲

信息学竞赛中的动态规划专题哈尔滨工业大学周谷越【关键字】动态规划动机状态典型题目辅助方法优化方法【摘要】本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫附录参考书籍与相关材料

1.动态规划的动机和基本思想首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】考虑在下面被显示的数字金字塔。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。【输入格式】第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。【输出格式】单独的一行包含那个可能得到的最大的和。【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层

动态规划试题

动态规划 1.最佳队形（bestqueue; 时限:1s; 128MB）【题目描述】要参加复赛了，大家都在体育馆门口集合完毕，由于这次参赛的人数较多，上车前需要排一下队，所有人自愿排成两队（分别定义为A和B队列，人数大于1且两队人数随意），Ms. Zhou给每位同学一张纸，每人默默写下一个字母代表自己，比如：郑逸宁写Z，吴天舒写W等等。 A队：字母：c m c B队：字母：s n m n 最佳队形为： 1、每个人前后可以有任意个空位，也可以没有空位； 2、两队在添加空位后长度必须一样，上图可以有多种方案使得A、B两队长度一致，例如： 3、根据每个人所写的字母，我们定义A队与B队的距离为相应位置上的字母的距离总和； 4、两队相应位置的距离定义为：

（1）两个非空位的距离定义为它们的所写字母ASCII码的差的绝对值；（2）空位与其他任意非空位之间的距离为已知的定值K；（3）空位与空位的距离为0。 5、最佳队形为：在A、B的所有可能队形中，必定存在两个等长的队A’、B’，使得A’ 与B’之间的距离达到最小，这个队形就是最佳队形。请你写一个程序，求出最佳队形时，A队与B队的距离。【输入数据】输入文件第一行为队列A每个人所写字母组成的字符串A；第二行为队列B每个人所写字母组成的字符串B。（约定：A、B均由小写字母组成且长度均不超过2000）。第三行为一个整数K（1≤K≤100），表示空位与非空位的距离。【输出数据】输出文件仅一行包含一个整数，表示所求得最佳队形A、B之间的距离。【样例】 bestqueue.in bestqueue.in cmc 10 snmn 2 2. 数学作业（homework; 时限:1s; 128MB）【问题描述】数学竞赛刚刚结束，据说题目很难，不过信息学里面的数学题也不容易哦，题目描述很简单：求：方程x1+2x2+…+nx n=m的所有非负整数解（x1,x2,…,x n）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、…、（0,0,0,0,1）。运用你的数学思维加上强大的信息学能力，试试解决它吧！【输入数据】 2个整数n，m 【输出数据】方程非负整数解的个数ans，如果解超过10^9，只需输出ans mod 10^9。

动态规划练习题合集(Dp-合集)

一、关键子工程（project.c/cpp/pas）在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、……、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：（1）根据预算，每一个子工程都有一个完成时间。（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。（4）整个工程的完成是指：所有子工程的完成。其中，表格中第I+1行J+2列的值如为0表示“子工程I”可以在“子工程J”没完成前施工，为1表示“子工程I”必须在“子工程J”完成后才能施工。上述工程最快完成时间为14天，其中子工程1、3、4、5为关键子工程。又例如，有五个子工程的工程规划表：上述的子工程划分不合理，因为无法安排子工程1，3，4的施工。输入数据：第1行为N，N是子工程的总个数，N≤200。第2行为N个正整数，分别代表子工程1、2、……、N的完成时间。第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、…、I-1、I+1、…N的依赖关系，（I=1、2、……、N）。每行数据之间均用一个空格分开。输出数据：

几个经典的动态规划问题

动态规划复习：《便宜的旅行》分析：这个问题很明显是一个动态规划的标准问题。考虑某一天晚上车队到达了终点，上一次的花销必然是只与早上车队所在的位置有关的。这样，由于要求从起点到终点最优的方案，所以从起点到达早上所出发时旅馆的方案也应该是最优的。以此类推，我们可以得出我们应该求出从起点到各个旅馆的最优方案。这样，如果我们设从起点到旅馆s i∈S (1≤ i≤ n)的最优方案的价值为f(s i)，就可以得到如下的动态规划方程： F(s[i])=min{f(s[j])}+value[i]; 0<=s[i]-s[j]<=800 这里value(s i)为s i的价值。《蛙人》设F(i,j) 是携带i升氧气，j升氮气的最小重量 F(i+a k,j+t k)=min{f(i,j)+W k}

李曙华同学程序 for i:=0 to 21 do for j:=0 to 79 do a[i,j]:=10000000; a[0,0]:=0; for i:=1 to n do begin readln(b[i,1],b[i,2],b[i,3]); for j:=21-b[i,1] downto 0 do for k:=79-b[i,2] downto 0 do begin if a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1]; if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k]; if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] then a[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3]; end; end; writeln(a[x,y]); close(input);close(output); end.

动态规划习题

动态规划专题分类视图数轴动规题： (1) 较复杂的数轴动规 (4) 线性动规 (7) 区域动规： (14) 未知的动规： (20) 数轴动规题：题1.2001年普及组第4题--装箱问题【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0

的个数，但不包括一个砝码也不用的情况。【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数. 第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量. 【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。【输入样例】 2 2 2 2 3 【输出样例】 Total=8 【样例说明】重量2,3,4,5,6,7,8,10都能秤得【数据限制】对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1 共s1个数，表示第一件衣服上每个破损修好它所需的时间第3行，为B1...Bs2 共s2个数，表示第二件衣服上每个破损修好它所需的时间第4行，为C1...Cs3 共s3个数，表示第三件衣服上每个破损修好它所需的时间第5行，为D1...Ds4 共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)

动态规划经典问题

动态规划经典问题 1、三角数塔问题设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。【代码】 // // 例题1 三角数字塔问题// // #include #include #define MAXN 101 intn,d[MAXN][MAXN]; int a[MAXN][MAXN]; voidfnRecursive(int,int); //递推方法函数声明 intfnMemorySearch(int,int); //记忆化搜索函数声明 int main() { inti,j; printf("输入三角形的行数n(n=1-100):\n"); scanf("%d",&n); printf("按行输入数字三角形上的数(1-100):\n"); for(i=1; i<=n; i++) for(j=1; j<=i; j++)

scanf("%d",&a[i][j]); for(i=1; i<=n; i++) for(j=1; j<=i; j++) d[i][j]=-1;//初始化指标数组 printf("递推方法：1\n记忆化搜索方法：2\n"); int select; scanf("%d",&select); if(select==1) { fnRecursive(i,j);//调用递推方法 printf("\n%d\n",d[1][1]); } if(select==2) { printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法} else printf("输入错误！"); return 0; } voidfnRecursive(inti,int j) //递推方法实现过程 { for(j=1; j<=n; j++) d[n][j]=a[n][j]; for(i=n-1; i>=1; i--) for(j=1; j<=i; j++) d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]); } intfnMemorySearch(inti,int j) //记忆化搜索实现过程 { if(d[i][j]>=0) return d[i][j]; if(i==n) return(d[i][j]=a[i][j]); if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1)) return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j))); else return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1))); } 2、硬币问题

动态规划：最短路径问题及程序

最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）； map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通；我们可以使用回溯法来计算DiS［x］： var S：未访问的城市集合； function search(who{x})：integer； {求城市who与城市E的最短距离} begin if Who＝E Then Search←0 {找到目标城市} Else begin min←maxint；{初始化最短路径为最大} for i 取遍所有城市 Do if（map[Who，i]＞0{有路}）and（i S{未访问}） then begin S←S－[i]；{置访问标志} j←map[Who，i]+ search(i)； {累加城市E至城市Who的路径长度} S←S＋[i]； {回溯后，恢复城市i未访问状态} if j＜min Then min←j； {如果最短则记下} end；{then} search←min；{返回最短路径长度} End；{else} End；{search} begin S←除E外的所有城市； Dis[a]←search（a）；{计算最短路径长度} 输出Dis[a]； end．{main} 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？

动态规划(生产和存储问题)

动态规划（生产和存储问题）一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=1.2….n.表示。