动态规划讲解大全Word下载.docx
《动态规划讲解大全Word下载.docx》由会员分享，可在线阅读，更多相关《动态规划讲解大全Word下载.docx（13页珍藏版）》请在冰点文库上搜索。
分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。
为了避免浪费，很显然，我们存放一个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?
最优性原理实际上是要求问题的最优策略的子策略也是最优。
让我们通过对前面的例子再分析来具体说明这一点：
从A到D，我们知道，最短路径是A
动态规划练习题
USACOSubsetSums
题目如下：
对于从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。
程序不能预存结果直接输出。
PROGRAMNAME:
subset
INPUTFORMAT
输入文件只有一行，且只有一个整数N
SAMPLEINPUT（file
7
OUTPUTFORMAT
输出划分方案总数，如果不存在则输出0。
SAMPLEOUTPUT（file
4
参考程序如下：
#include<
fstream>
usingnamespacestd;
constunsignedintMAX_SUM=1024;
intn;
unsignedlonglongintdyn[MAX_SUM];
ifstreamfin（"
"
）;
ofstreamfout（"
intmain（）{
fin>
>
n;
（）;
ints=n*（n+1）;
if（s%4）{
fout<
<
0<
endl;
（）;
return;
}
s/=4;
inti,j;
dyn[0]=1;
for（i=1;
i<
=n;
i++）
for（j=s;
j>
=i;
j--）
dyn[j]+=dyn[j-i];
（dyn[s]/2）<
return0;
USACOLongestPrefix
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。
生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。
如果一个集合P中的元素可以通过串联（允许重复；
串联，相当于Pascal中的“+”运算符）组成一个序列S，那么我们认为序列S可以分解为P中的元素。
并不是所有的元素都必须出现。
举个例子，序列ABABACABAAB可以分解为下面集合中的元素：
{A,AB,BA,CA,BBC}
序列S的前面K个字符称作S中长度为K的前缀。
设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。
prefix
输入数据的开头包括1..200个元素（长度为1..10）组成的集合，用连续的以空格分开的字符串表示。
字母全部是大写，数据可能不止一行。
元素集合结束的标志是一个只包含一个“.”的行。
集合中的元素没有重复。
接着是大写字母序列S，长度为1..200,000，用一行或者多行的字符串来表示，每行不超过76个字符。
换行符并不是序列S的一部分。
AABBACABBC
.
ABABACABAABC
只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。
11
示例程序如下：
#defineMAXP200
#defineMAXL10
charprim[MAXP+1][MAXL+1];
intnump;
intstart[200001];
chardata[200000];
intndata;
intmain（intargc,char**argv）
{
FILE*fout,*fin;
intbest;
intlv,lv2,lv3;
if（（fin=fopen（"
"
r"
））==NULL）
perror（"
fopenfin"
exit
（1）;
if（（fout=fopen（"
w"
fopenfout"
while
（1）
fscanf（fin,"
%s"
prim[nump]）;
if（prim[nump][0]!
='
.'
）nump++;
elsebreak;
ndata=0;
while（fscanf（fin,"
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）;
USACOScoreInflation
我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
我们可以从几个种类中选取竞赛的题目,这里的一个"
种类"
是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。
你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入包括竞赛的时间,M（1<
=M<
=10,000）和N,"
的数目1<
=N<
=10,000。
后面的每一行将包括两个整数来描述一个"
:
第一个整数说明解决这种题目能得的分数（1<
=points<
=10000）,第二整数说明解决这种题目所需的时间（1<
=minutes<
=10000）。
你的程序应该确定我们应该从每个"
中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的"
的题目数目可能任何非负数（0或更多）。
计算可能得到的最大分数。
inflate
第1行:
M,N--竞赛的时间和题目"
的数目。
第2-N+1行:
两个整数:
每个"
题目的分数和耗时。
3004
10060
250120
120100
3520
单独的一行包括那个在给定的限制里可能得到的最大的分数。
605
{从第2个"
中选两题，第4个"
中选三题}
ifstreamfin（"
ofstreamfout（"
constshortmaxm=10010;
longbest[maxm],m,n;
void
main（）
shorti,j,len,pts;
m>
for（j=0;
j<
=m;
j++）
best[j]=0;
for（i=0;
i++）{
pts>
len;
for（j=len;
if（best[j-len]+pts>
best[j]）
best[j]=best[j-len]+pts;
best[m]<
第二行：
N个整数，分别表示每首歌的长度，按创作时间顺序排列。
452
4342
一个整数，表示可以装进M张CD盘的乐曲的最大数目。
3
#defineMAX25
intdp[MAX][MAX][MAX],length[MAX];
int
main（）
FILE*in=fopen（"
FILE*out=fopen（"
inta,b,c,d,best,numsongs,cdlength,numcds;
fscanf（in,"
%d%d%d"
&
numsongs,&
cdlength,&
numcds）;
for（a=1;
a<
=numsongs;
a++）
%d"
length[a]）;
for（a=0;
numcds;
for（b=0;
b<
=cdlength;
b++）
for（c=0;
c<
c++）{
for（d=c+1;
d<
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{
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"
解决背包问题
动态规划的定义：
动态规划的基本思想是把待求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解得到原问题的解，其中用动态规划分解得到的子问题往往不是互相独立的。
动态规划在查找有很多重叠子问题的情况的最优解时有效。
它将问题重新组合成子问题。
为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。
因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。
最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。
简单地说，问题能够分解成子问题来解决。
求解步骤如下：
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
升级会员 