|
常用算法之动态规化专题
1. 动态规划的概念
在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。
与穷举法相比，动态规划的方法有两个明显的优点:
(1)大大减少了计算量
(2)丰富了计算结果
动态规划的最优化概念是在一定条件下，找到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。
应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。
2. 动态规划适合解决什么样的问题
准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。
或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。
上面所说的“满足一定条件”主要指下面两点：
(1)状态必须满足最优化原理；
(2)状态必须满足无后效性。
动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。
动态规划的无后效性原则某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。
3. 为什么要用动态规划法解题
首先，看下面一个问题:
【例题1】数字三角形问题。
7
3 8
8 1 0
2 7 7 4
5 5 2 6 5
如上所示出的一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。
如输入： 5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
输出：30
【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：
下载:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。
4.怎样用动态规划法解题
(1).逆推法:
按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。
设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；
则: f[n,j]=a[n,j] 1<=j<=n
f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i.
f[1,1]即为所求。
程序如下：
载:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
顺推法
按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值设f[i,j]为 第i行第j列上点到起点的最大和则 f[1，1]=a[1,1];
f[i，1]=a[i, 1]+f[i-1,1];
f[ i，j ]=max{ a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i
max(f[n,1],f[n,2],.......,f[n,n]}即为所求。
程序如下:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
说明一下：
1.用动态规划解题主要思想是用空间换时间.
2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.
程序如下:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
练习:用一维数组和逆推法解本题.
5.用动态规划法解题的一般模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
┌───┐┌───┐┌───┐
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
└───┘└───┘└───┘
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。
根据上述动态规划设计的步骤，可得到大体解题框架如下:
1.初始化(边界条件)
2.for i:=2 to n (顺推法) 或 for i:=n-1 to 1(逆推法)
对i阶段的每一个决策点求局部最优
3.确定和输出结束状态的值.
练习一、求最长不降子序列
（1）问题描述
设有由n个不相同的整数组成的数列，记为:
a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1• 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；
2• 若从a(n-1)开始查找，则存在下面的两种可能性：
①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3• 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:
在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。
4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号
(3) 程序如下:（逆推法）
:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar练习二、背包问题
背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.
本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
2.0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数
设 f(i，x)表示前i件物品，总重量不超过x的最优价值
则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;
动态规划方法(顺推法)程序如下:
程序如下： :本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
练习三、完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法） 程序如下： color=#FF1493]本专题源程:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
另外一个问题: 最短路径
问题描述： 求v1到v10的最短路径长度及最短路径。
图的邻接矩阵如下：
0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 13 12 11 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0
采用逆推法
设f（x）表示点x到v10的最短路径长度
则 f(10)=0
f(x)=min{ f(i)+a[x,i] 当a[x,i]>0 ,x<i<=n}
程序如下:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
练习题四、
1.求一个数列中的连续若干个数和的最大值.
本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar2.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。
本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
3. 装箱问题
问题描述:有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
样例
输入： 24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n 个物品的各自体积
3
12
7
9
7
输出：0 一个整数，表示箱子剩余空间。
方法三、原始递归法
先看完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-i)+c[i]} 当x>=w[i] 1<=i<=n
可使用递归法解决问题程序如下: ()
说明:当m不大时,编程很简单,但当m较大时,容易超时.
本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar4.2 改进的递归法
改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个
一维数组即可
程序如下:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
习题
用改进的递归法解资源分配问题:
n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。
练习一例:乘积最大问题 问题描述：
今年是国际数学联盟确定的"2000--世界数学年"，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手除了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字川：312，当N=3,K=1时会有一下两种分法：
1） 3*12=36
2） 31*2=62
这时，符合题目要求的结果是；31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入：
程序的输入共有两行：
第一行共有2个自然数N，K（6≤N≤50，1≤K≤20）
第二行是一个长度为N的数字串。
输出：
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
样例：
输入
4 2
1231
输出
62
程序如下:本专题源程http://www.shimne.net/ioi/ycx/dtgh.rar
再看一示例：
统计单词个数
[问题描述]
给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字串分成k份（1<k≤40），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，选用this之后就不能包含th）。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
[输入格式]
全部输入数据存放在文本文件input3.dat中，其格式如下：
第一行为一个正整数(0<n≤5)表示有n组测试数据
每组的第一行有二个正整数：（p,k)
p表示字串的行数；
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）
接下来的s行，每行均有一个单词。
[输出格式]
结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。
[样例]
输入：1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出： //说明：（不必输出）
7 // this/isabookyoua/reaoh
sab
赛题示例2002年第四题：
求：平面上的n个点用k个矩形覆盖的最小面积？ |
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
