动规dp理论动态基础篇

动态规划算法在近几年的各级信息学竞赛中代替了搜索算法的地位，成为为了使能熟练、透彻地掌握这种算法。我们通过动态规划准备篇、基础篇、中级篇和动态规划基础篇110的最短路径。1101与结点445连的情况。110外，其它各阶段的结点既是上一阶段的终点，又是下一阶段7、8、9中某结点的起点。第三阶段第四阶段101逆向来推导：即第五阶段由第四阶段推出，第ab1两点距离。2ab1两点距离。2345678911101-3-51-2-5的。也就是说，当某阶段结点一定11到阶段2、3、4、5各结点的最短距离，最终得出答案。在计算过程中，到某阶段上一结点的决策，156，658min{6+5,5+5}即7 也可写成一个递推：n表示行数，max(n)表示第n行的最大值，首先我们设data(i,j)为(i,j)位置的数据，sum(i,j)为到达该点的最大数字和。有如下：在n行数字三角形中 sk的取值集合称为状态集合，用Sk表示。S4={⑦,⑧,⑨}。34的⑧状表示决策的变量决策变量常用uk(sk表示第k阶段当状态为sk时的决策变量。Dk(sk表示第kskuk(skDk(sk)。3的⑤状态出发有两条路，也就是两个决策，分别导向阶段4的⑦、⑧两个状态，即D3(⑤)={⑦,⑧}kskuk共同确定第k+1sk+1的过程叫状态导。货郎担问题是对平面给定的n个点确定一条连结各点的闭合的 图5(a)给出了七个点问题的解。Bitonic旅行路线问题是 对于货郎担问题,阶段与阶段之间没有什么必然的NP完全问题，其解决的时间复杂度很可能是指数级的。Dk+1，Dk+2，…，Dn也是最优的。例1：在引例1中我们寻找一条最短路径1－3－6－8－10；那取任何一个寻找出的最短3－6－838的最短路径，而不是其它路IJACB到C法证明：假设有另一路径J’B到C的ACI和J’I和J更优，这与原名题。从而证明J’必是B到C的最优路径4所得余数最小的路径为最优路径。求一条最优路径。1的思维，A最优取值可以由B的最优取值来确定B的最优取0A的最优值径的子路径，也就是说，AB的最优取值决定的，其不具有最优子结构。1k点的长度mod4sk的路径是否存在，用fk(sk)来表示，则递推如下lenkik-1ki条边的长度，方括号表示“或(or)”运算。f4(s4)s4值。这个递推法的递推和动态规划的规划方程非常相似，我们在这里借用了动态规划的fk(sk) ukDk(skskk段的某个状态，ukskDk(sk)中的一个决策，Tk(sk,uk)skukk+1sk1，g(x,uk)x和决策uk上的一个函数，而optmaxmin。fn(sn)某个初始值值，但是一般在实际应用中我们通常将该递归改为递推求解，这样一般效率会更高fk(sk)

fk1(uk指向的点sk1)边uk的长度f4(D1)动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含)(3)按自底向上或自顶向下化的方式计算最优值。0/1背包问题。为子问题的思维框框，提供一种新的思维方式。在正向思维法中，我们不再区分原问题问题，将动态规划的过程看成是从状态到状态的转移。所有的状态构造出一个状态空在后面的“最短路问题”当中，结合最短路问题来示范动态规划的正向思维法。动态规划的正向思维法带给我们什么启示呢?在应用动态规划求解的问题的过程中，希望能够注意从题目的分析中：应用对f1(s1)初始化（边界条件fork2ton（这里以顺序求解为例fk(sk)一个极值（∞或sk-t(fk-1(sk- t比fk(sk)更 据的决策从目标状态的决策开始向后找出所有的决策即为最优策略。该法的特点需要大T1，T2，T3，T4，T5代表终点，试找出一条从起点到终点的最短路径。如图中所的S4->A3->B3->C2->T3最短路径的长度为26。Max=300最多的城市数Inputfile='F:\input.Txt';{输入文件名}Outputfile='f:\output.Txt';{输出文件名} ;{最大整数}TypeMaps=Array[1..Max,1..Max]Ofinteger地图变量}Se:SetOfByte;{未过的城市集合}Dis:Array[1..Max]OfLongint;{某城市到终点城市的最短距离}Fr:Array[1..Max]Ofinteger;{动态规划的标识数组}Bo:Array[1..Max]OfBoolean;{过城市标识}N,M:Integer;{输入数据,N个城市，M条路}F:Text;{文件变量}ProcedureInit初始化过程}ForI:=1ToMDoProcedureMain动态规划”递推过程}I,J,WhoMinLongint当前最小值}Dis[N]:=0初始化动态规划数组}fori:=ndownto1Forj:=1ToNDo{利用“状态转移方程”递推结果}IfMap[I,J]>0ThenIf(Fr[I]=0)Or(Dis[I]>Dis[J]+Map[I,J])ProcedurePrint;{输出结果决策法}VarI:Integer; WhileI<>NDo Init输入Print输出Max=300最多的城市数Inputfile='F:\input.Txt';{输入文件名}Outputfile='f:\output.Txt';{输出文件名} ;{最大整数}TypeMaps=Array[1..Max,1..Max]Ofinteger地图变量}Se:SetOfByte;{未过的城市集合}Dis:Array[1..Max]OfLongint;{某城市到终点城市的最短距离}Fr:Array[1..Max]Ofinteger;{动态规划的标识数组}Bo:Array[1..Max]OfBoolean;{过城市标识}N,M:Integer;{输入数据,N个城市，M条路}F:Text;{文件变量}ProcedureInit初始化过程}ForI:=1ToMDoProcedureMain动态规划”递推过程}I,J,WhoMinLongint当前最小值}Dis[N]:=0初始化动态规划数组}WhileWho<>1DoForI:=1ToNDo{利用“状态转移方程”递推结果}IfMap[I,Who]>0ThenIf(Fr[I]=0)Or(Dis[I]>Dis[Who]+Map[I,Who])ThenMin:=Big;{1Bo标志数组ForI:=1ToNIfBo[I]And(Fr[I]>0)And(Dis[I]<Min)ThenProcedurePrint;{输出结果决策法}VarI:Integer; WhileI<>NDo Init输入Print输出程序实现：按这个 ;{Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名}TypeMaps=Array[1..Max,1..Max]Ofinteger数字矩阵}N:Integer输入数据,N行}F:Text;{文件变量}ProcedureInit初始化过程ForI:=1tonDoforj:=1toidoProcedureMain“动态规划”递推过程Dis:=map初始化动态规划数组}fori:=n-1downto1doforj:=1toiIf(Dis[i+1,j]>Dis[i+1,j+1])Then elsebeginProcedurePrint输出结果}Vari,j:Integer; fori:=1ton-1doInit输入Print输出max c1，c2，…，cna1，a2，…，anb第一问：maxZx1，x2，…，xn的各个值（xi是非负整数，i=1,2,…n）x1，x2，…，xn的各个值没有限制，①我们给c1c2，…cn

c1’，c2’，…，cna

a

a

a

a

a1

2

n

1

2

na②我们取c1’aixi=bdivai；b=b-aa1 b>0我们取c2’ai’xibdivai’；b=b-ai’*xi a推

2b=0a值都被寻找。第二问：maxZx1，x2，…，xn的各个值（xi=0，1）Z

{Zi-1(x),Zi-1(x- (x<0)（i=1,2,…nx1，x1=6推出maxZ=12，x1，x2，x36，0，0。Z1(0)=max{Z0(0),Z0(-1)+2}=max{0,-Z2(0)=max{Z1(0),Z1(-2)+3}=max{0,-Z2(1)=max{Z1(1),Z1(-1)+3}=max{2,-Z3(0)=max{Z2(0),Z2(-5)+4}=max{0,-Z3(1)=max{Z2(1),Z2(-4)+4}=max{2,-Z3(2)=max{Z2(2),Z2(-3)+4}=max{3,-Z3(3)=max{Z2(3),Z2(-2)+4}=max{5,-Z3(4)=max{Z2(4),Z2(-1)+4}=max{5,-（54）0/1品的重量为wipiZi(x)=0x

{Zi-1(x),Zi-1(x- (x<0)（i=1,2,…ni1～n，x0～bxx-aiZi(x)=-∞(x<0)；如何处理呢？看看程序吧。Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名} data=array[0..100,0..10000]oflongint;r:array[0..100,0..10000]ofboolean;weight,code:array[1..100]ofinteger;ProcedureInit初始化过程}fori:=1tondofori:=1tondoproceduremain;vari,j,k,t:integer;fori:=1tondo

ProcedurePrint输出结果}Varj,i:integer;whilei<>0doifr[i,j]thenwrite(f,'1');elsewrite(f,'0');forj:=1tototaldoifk<0thenbegink:=0;t:=-1ifdis[i-1,j]>dis[i-1,k]+code[i]*tthendis[i,j]:=dis[i-1,j]elsebeginInit输入Print输出Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名}varweight,code,x:array1..100ofinteger;{weight记录物体的重量，code记录物体的价值，x所求的解}procedureinit;{读入数据}vari,w:integer;fori:=1tondofori:=1tondofunctionvart0,t1:integer;

ifc<0thenfac:=-maxintelseifk=0thenfac:=0elsebeginift1>t0thenelsebeginProcedurePrint输出结果}Varj,i:integer;a:array[1..100]ofinteger;（55）

an个项目，gi(x)x（x<=a）i所能得到的利润，i=1，2，…，n最合理的资源分配导致解下面的问题：max其中 xi>=0，i=1，2，…，n1234567ABCf

ff

{g2(x)+f1(a-{g3(x)+f2(a-f

{gn(x)+fn-1(a-1Aa与利润f1(a)（af1234567得到f1(7)=0.36，2、考虑投到A、B两种产品的生产a与利润f2(a)关系如表，其中x2为投到产品，的生产（表012345671234567得到f2(7)=0.523、考虑投到A、B和C三种产品的生产，a与利润关系如表，其中x3为投到产CC01234567f2(a-得到f3(7)=0.68O(n3)，还是比较高的。Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名} data=array[0..100,0..10000]oflongint;m,n:Integer输入数据,m个投资项目，n个资源数目}F:Text;{文件变量}ProcedureInit初始化过程}fori:=1tomdoforj:=1tondoProcedurePrint输出结果}Varnum,i:integer;whilei<>0do

proceduremain;vari,j,k:integer;fori:=1tondoli[1,i]:=i;fori:=2tomdoforj:=0tondofork:=0tojdoifdis[i,j]<dis[i-1,j-k]+zi[i,k]thenInit输入Print输出（56）213n213n1111232333（0<pj(xj)<1cjjajjac分别表示允许重量和代价的上限；maxncjxj

ajxjj1

a；xj为正整数，j=1，2，…，nS，分别用的三种D1，D2，D3的价格与可靠性如下： 令fi(uivi表示第i级允许重量上限为vi，代价上限为ui时的最高可靠性。则f1(u(1),v(1)

u1 y1=minca}1 1fk(u(k),v(k)

max[pk(xk)*fk-1(u(k)-ckxk,v(k)-akxk)]0xkuk v0xk其中yk=mincak k以上例：D3的可靠性为0.9，失败的概率为1-0.9=0.1，x3个元件并联全部失败的概(0.1)x3，1-(0.1)x3是至少一个工作正常的概率。1x31x3

[1-(0.1)x3×f2(220-60x3而

[1-(0.2)x2×f1(u-30x2uy2=30

y1=20 160①u=160时，y230 u=130时，y1=3；f1(130)=max{0.5,0.75,0.875}；u=70时，y1=1；f1(70)=max{0.5}；u=40时，y1=1；f1(40)=max{0.5}；u=10时，y1=0；f1(10)=0；100②u=100时，y230 u=70时，y1=1；f1(70)=max{0.5}；u=40时，y1=1；f1(40)=max{0.5}；u=10时，y1=0；f1(10)=0；40③u=40时，y230 x1=2，x2=2，x3=12000.648。='';{Outputfile='f:\output.Txt';{名TypeMaps=Array[1..Max,1..Max]Of

lu:Array[1..Max]Ofintegercode,kekao:Array[1..Max]Ofreal;F:Text;{文件变量}ProcedureInit初始化过程}ForI:=1TonDoRead(F,code[i]);Fori:=1TonDoRead(F,kekao[i]);functionMain(i:integer;u:real):real;Varj,k,m:integer;k:=trunc(u)divtrunc(code[i]);ifi<>1thenforj:=1tokdoform:=1tojdop:=p*p1;iftemp>mainthen（56）

elseforj:=1tokdoform:=1tojdop:=p*p1;ifp>mainthenmain:=pProcedurePrint输出结果}VarI:Integer;Init;{输入}Print输出}A1A2…Ai-1AiAi1…AnAi-1AiAi1ri-1*riri*ri+1，ri+1*ri+2的矩阵。我们要计算的就是这种特殊矩阵相乘所需的最小的运算A、B和CA=(aij)m*n，B=(bij)n*t，C=(cijt*rABC。AB第一种乘法次数为：(Am*nBn*t)Ct*r=Dm*tCt*r=mnt+mtr；第二种乘法次数为：Am*n(Bn*tCt*rAm*nDn*r=mnr+ntr；m=10，n=100，t=5，r=50，则第一种mnt+mtr=5000 第二种mnr+ntr=50000 1Cn同运算次序方案数为Catalan数Cn-1= 2n2；显然，通过所有加括号的方案的枚举和根据动态规划的最优化原理，如果最佳方案形式为(A1A2…AiAi+1Ai2…An)，则A1A2…Ai和Ai1Ai2…AnmijAiAi1…Aj所需的最小乘法次数。AiAi+1…Aj=(AiAi+1…Ak)(Ak+1Ak+2ikmij=min{mik+m(k+1)j+rirk+1rj+1}；ik2km12=min{m11+m22+r1r2r3}=35*40*20=28000；m23=min{m222k3k

2k

最佳方案为((A1(A2A3))A4)乘法次数为27250Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名}typer:array[1..max]ofinteger;dis:array[0..max,0..max]oflongint;A:array[1..max]ofrec;N:Integer输入数据}F:Text;{文件变量}ProcedureInit初始化过程}ForI:=1ton+1Do

procedureprint;vari,j:integer;fori:=2ton-1dowrin(f,a[i].i1,'',a[i].k1);ProcedureMain“动态规划”递推过程forj:=1ton-1dofori:=1ton-jdofork:=itoi+j-1doifdis[i,i+j]=0thenelseIfDis[i,i+j]>(Dis[i,k]+dis[k+1,i+j]+r[i]*r[k+1]*r[i+j+1])ThenbeginInit输入Print输出A={a1，a2，…，am}B={b1，b2，…，bn}，若存在单调递增的整数i1<i2<…<i{ai1ai2…ait{bi1bi2…bitk1,2,…,tC={c1，c2，…，ct}CABttAB的最长公共子序列。LCS(A,B)表示。例如：A={d,b,c,b,a,d,b}B={b,a,c,d,b,d}C1={b,a,d}AB的公共子序列，但C2={b,a,d,b}C3={b,c,d,b}4，4C2C3便是最长的公共子序列。最长的公共子序列 i=0或 LCS=(Ai-1,Bj- max{LCS=(Ai-1,Bj),LCS=(Ai,Bj- i0123450000000010000111201111223011222240112233501222336012233470122344（3（7（2（3（3（6（3（ai=bj时lcs(i,j)←lcs(i,j)←lcs(i1,j1)+1ai≠bj但lcs(i-1,j)>=lcs(i,j-1)时，lcs(i,j)←lcs(i-1,j)ai≠bjlcs(i1,j)<lcs(i,j1)时，lcs(i,j)←lcs(i,j-1)。Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名}lcs:array[0..255,0..255]oflongint;F:Text;{文件变量}ProcedureInit初始化过程}

procedureprint;vari,j,m:integer;

while(i<>0)and(j<>0)doif(a[i]=b[j])thenelseiflcs[i-1,j]>=lcs[i,j-1]theni:=i-1elsej:=j-1fori:=mdownto1dowrite(f,t[i],'');ProcedureMain“动态规划”递推过程whilei<=ladowhilej<=lbdoifa[i]=b[j]thenlcs[i,j]:=lcs[i-1,j-elseiflcs[i-1,j]>=lcs[i,j-1]thenlcs[i,j]:=lcs[i-1,j]elselcs[i,j]:=lcs[i,j-1];Init输入Print输出问题描述：设有一个正整数的序列：b1，b2，…，bn，对于下标i1，i2，…，im，若有bi1<=bi2<=…<=bimm的不下降序列。例如：有下列数列：、、、、、、、、、、21、22、63、15。对于下标i1=2i2=3i3=4i4=8i5=9i6=11i7=12i8=13，且满足7<9<16<18<19<21<22<638的不下降序列。这个序列是我们所求的最长123456789000000000000002222，最长的做为，修改22的长度和指针。1100再到数项21，在它的后面有3项，因此必 为最长的做为，由于22，63都大于21，但22的长度为2，63的长度为1，所以选择22做为它的。后，21的长度为3，为12，表示到21之后，还有数据项22，到了22之后，还有63，到了63之后，由于为0，所以结束。如右图。（1 2345678913434897900值和值。可参见下面给出的三个程序中的不同数据结构的表示，虽然不同，但意{Inputfile='F:\input.Txt';{输入文件名}Outputfile'f:\output.Txt输出文件名}a,lcs,r:array[0..1000]ofinteger;F:Text;{文件变量}ProcedureInit初始化过程}fori:=1tondoread(F,a[i]);procedureprint;vari,j,max:integer;fori:=1toniflcs[i]>maxthen whilej<>0do{='';{Outputfile='f:\output.Txt';{名a,lcs:array[0..1000]ofinteger;F:Text;{文件变量}ProcedureInit初始化过程}

write(f,a[j],'');ProcedureMain动态规划”递推过程fori:=1tondolcs[i]:=1;fori:=n-1downto1doforj:=ndowntoi+1if(a[j]>a[i])and(lcs[j]>m)thenInit输入Print输出fori:=1tondoread(F,a[i]);procedureprint;vari,j,max:integer;fori:=1toniflcs[i]>maxthen whilei>0doWhilelcs[j]<>idoinc(j);write(f,a[j],'');{3}constmaxn=100;Inputfile='F:\input.Txt';Outputfile'f:\output.Txt';typetlist=array[1..maxn,1..3]ofinteger;vard:tlist;procedureinit;vari:integer;fori:=1tondoproceduremake;fori:=n-1downto1do

proceduremain分解并输出}varI,J:integer;a[n+1]:=maxint设置边界}fori:=ndownto0 {逆推求解forj:=1+iton+1do{输出if(lcs[j]>=lcs[i])and(a[j]>=a[i])thenlcs[i]:=lcs[j]+1;Init输入forj:=i+1tonif(d[i,1]<d[j,1])and(d[j,2]>l)thenifl>0thenprocedureoutput;vari,l,dmax:byte;fori:=2ton-1ifd[i,2]>dmaxthenwrin(f,'maxlength=',dmax);whilel<>0do

（55）问题描述：工厂生产某种产品，每单位(千件)1(千元)，每次开工的固定成本为2，3，2，4(千件)。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于第三四季度才能上市的产品需付费，每季每千件的费为0.5(千元)还规定年初和年末这种产品均无库存试制订一个生产计划，时的量xk，每个阶段的产量u