4种常见的动态规划模型

1、例谈四种常见的动态规划模型动态规划是解决多阶段决策最优化问题的一种思想方法，本文主要结合一些例题，把一些常见的动态规划模型，进行归纳总结。（一）、背包模型可用动态规划解决的背包问题，主要有01背包和完全背包。对于背包的类型，这边就做个简单的描述：n个物品要放到一个背包里，背包有个总容量m，每个物品都有一个体积wi和价值vi，问如何装这些物品,使得背包里放的物品价值最大。这类型的题目，状态表示为：fj表示背包容量不超过j时能够装的最大价值，则状态转移方程为：fj:=maxfj-wi+vi,边界：f0:=0;简单的程序框架为：beginreadln(m,n);for i:=1 to n do re

2、adln(wi,vi);f0:=0;for i:=1 to m dofor j:=1 to n dobeginif i>=wj then t:=fi-wj+vj;if t>fi then fi:=t;end;writeln(fm);end.这类型的题目应用挺广的（noip1996提高组第4题，noip2001普及组装箱问题，noip2005普及组采药等），下面一个例子，也是背包模型的简单转化。货币系统(money)【问题描述】母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。他们对货币的数值感到好奇。传统地，一个货币系统是由1，5，10，20或25，50，100的单位面

3、值组成的。母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。使用一个货币系统1,2,5,10,.产生18单位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一个确定的面值。【输入格式】货币系统中货币的种类数目是v(1v25)；要构造的面值是n(1n10,000)；第1行:二个整数，v和n；第2.v+1行：可用的货币v个整数(每行一个)。【输出格式】单独的一行包含那个可能的构造的方案数。 【输入样例】 3 10125【输出样例】10分析：此题是

4、个背包模型，只是问题的解是构造方案数,设wj为第j种币值，状态fi：构造面值为i时可能的方案数，则状态转移方程为：fi:=fi-wj，i>=wj,边界：f0:=1;fn即为问题的解。注意：由于此题的数据规模比较大，所以要用到高精度加法，估计最大的数据可以达到73位，为节约程序时间和空间效率，还采用了万进制的高精度加法。参考程序如下：varf:array0.10000,1.20of integer;long:array0.10000of integer;/存储位数w:array0.25of integer;n,m,i,j,k:integer;procedure add(r,t:intege

5、r);/万进制高精度加var i,k:integer;beginif longt<longr then longt:=longr;k:=0;for i:=1 to longt do beginft,i:=(ft,i+fr,i+k);k:=ft,i div 10000;/每一个存4位,万进制，这样省时省空间ft,i:=ft,i mod 10000;end;while k>0 do/进位处理begininc(longt);ft,longt:=k mod 10000;k:=k div 10000;end;end;procedure main;var i,j:integer;beginf0

6、,1:=1; long0:=1;for i:=1 to m dofor j:=wi to n do add(j-wi,j);write(fn,longn);/输出答案,由于每个存4位,所以有时需要补零for i:=longn-1 downto 1 dobeginif fn,i<10 then write('000')else if fn,i<100 then write('00')else if fn,i<1000 then write('0');write(fn,i);end;end;beginassign(input,

7、9;money.in');reset(input); assign(output,'money.out');rewrite(output);readln(m,n);for i:=1 to m do readln(wi);main;close(input);close(output);end.（2） 、资源分配模型这类型的题目一般用资源数做状态，数组fi,j表示前个i个部门分配j个资源的最大盈利，则状态转移方程为：fi,j:=maxfi-1,k+valuei,j-k (0<=k<=j)程序框架如下：var i,j,k:longint;beginfor i:=1

8、 to n dofor j:=0 to m dofor k:=0 to j doif fi-1,k+valuei,j-k>fi,j then fi,j:=fi-1,k+valuei,j-k;writeln(fn,m);end;资源分配类型典型应用是花店橱窗(flower.pas)设置，没做过的同学可以自己去练习一下，下面的一个例题，也是此类型的转换。问题描述农夫ion放完马以后，需要把马儿关回马厩。为了做好这件事，ion让马排成一行跟着他入马厩。他想出了一个就近入厩的办法：让前p1匹马进入第一个马厩，然后的p2匹马进入第二个马厩，如此类推。而且，他不想让任何一个马厩（共k个）留空，还有所

9、有的马都进入马厩。已知ion只有黑色和白色两种颜色的马，然而并不是所有的马都能相处融洽。假如有i匹黑马和j匹白马同在一个马厩，那么它们之间的不愉快系数为i*j。马厩总的不愉快系数等于k个马厩的不愉快系数之和。请帮忙把n匹马按顺序放入k个马厩中（即求一种 p1,p2的安排方案），使得总的不愉快系数最小。输入格式输入第一行为一个n和k；（n<=100,k<=n）;输入第二行为n个数0和1，0表示白马，1表示黑马输出格式一行，最小的不愉快系数。样例输入3 21 0 1样例输出1分析：设fi,j：表示将前i匹马放入前j个马厩，得到的最小不愉快系数。wi,j：表示将第i至第j匹马放入同一个马

10、厩所得到的不愉快系数。状态转移方程为：fi,j=min(fk,j-1+wk+1,i)j-1<=k<i注意边界条件：fi,1:=w1,i;fi,i:=0;参考程序如下：const maxn=100;maxk=100;varf:array1.maxn,1.maxkof longint;w:array1.maxn,1.maxnof longint;a:array1.maxnof longint;i,j,k,k1,n,s1,s2:integer;beginassign(input,'horse.in'); reset(input);assign(output,horse.o

11、ut); rewrite(output);readln(n,k);for i:=1 to n do read(ai);for i:=1 to n do/求 wi,jfor j:=i to n dobegins1:=0;s2:=0;for k1:=i to j doif ak1=0 then inc(s1) else inc(s2);wi,j:=s1*s2;end;for i:=1 to n do/ 初始化for j:=1 to k dofi,j:=maxint;for i:=1 to n do/边界条件beginfi,i:=0;fi,1:=w1,i;end;for j:=1 to k do/动

12、规过程for i:=j to n dofor k1:=j-1 to i-1 doif (k1>0) and (j-1>=1)and (fk1,j-1<>maxint)thenfi,j:=min(fk1,j-1+wk1+1,i,fi,j)writeln(fn,k);close(input);close(output);end.（三）、区间类模型区间类模型的动态规划，一般是要求整段区间的最优值，子问题一般是把区间分成两个子区间。一般用二维数组表示状态，例如fi,j表示从i到j的最优值。则状态转移方程就是跟子区间之间的关系，下面我们用个典型的例子讲解这个模型的应用。问题描述给

13、定一个具有n（n<50）个顶点（从1到n编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成n-2个互不相交的三角形，使得这些三角形顶点 的权的乘积之和最小？输入文件：第一行顶点数n第一行n个顶点（从1到n）的权值输出格式：最小的和的值,各三角形组成的方式输入示例：5122 123 245 231输出示例：the minimum is :12214884the formation of 3 triangle:3 4 5,1 5 3,1 2 3分析:这是一道很典型的区间模型动态规划问题。设fi,j（i<j）表示从顶点 i 到顶点 j 的凸多边形三角剖分后所得到的最大乘积，

14、我们可以得到下面的动态转移方程：fi,j=minfi,k+fk,j+si*sj*sk(i<k<j)目标状态为：f1,n但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形甚至实形的范围，所以我们还需用高精度计算，但这是基本功，程序中就没有写了，请读者自行完成。参考程序vars:array1.50 of integer;f:array1.50,1.50 of comp;d:array1.50,1.50 of byte;n:integer;procedure init;var i:integer;beginreadln(n);for i:=1 to n do read(

15、si);end;procedure dp;/动态规划var i,j,k:integer;beginfor i:=1 to n dofor j:=i+1 to n do fi,j:=maxlongint;/赋初始值for i:=n-2 downto 1 dofor j:=i+2 to n dofor k:=i+1 to j-1 doif (fi,j>fi,k+fk,j+si*sj*sk) thenbeginfi,j:=fi,k+fk,j+si*sj*sk;di,j:=k; /记录父节点end;end;procedure print(i,j:integer);/输出每个三角形beginif

16、j=i+1 then exit;write(',',i,' ',j,' ',di,j);out(i,di,j);out(di,j,j);end;procedure out;/输出信息beginwriteln('the minimum is :',f1,n:0:0);writeln('the formation of ',n-2,' triangle:');write(1,' ',n,' 'd1,n);out(1,d1,n);out(d1,n,n);end;begin/

17、主程序init;dp;out;end.区间模型的动态规划，在历届的信息学竞赛，应用非常广泛，如noi95的石子合并问题，noip2003普及组的数字游戏，noip2006提高组第1题等。（四）树型动态规划模型上面三种动态规划都是建立在线性结构上的，有顺推和逆推两种方法，下面我们介绍 一种建立在树这个数据结构上的动态规划树型动态规划模型。树型动态规划是建立在树结构上的动态规划，所以阶段很明显，一般是通过孩子节点的最优值推出父亲节点的最优值。一般以节点及相关信息为状态，动态转移方程是也是根据父亲节点跟孩子节点之间关系来建立的。通过根的子节点传递有用的信息给根，完后根得出最优解的过程。下面结合一些例

18、子，来介绍它的一般解法。例1:问题描述给你一棵树T=(V,E,W)，其中V表示顶点集且|V|=n，E表示边集。如果<v,u>属于E，则W<v,u>表示<v,u>的长度。求两点v,u，使得它们之间的路径总长度最长。你只需要输出这个最长长度即可。输入格式:输入第1行为n和边数e接下来e行，每行三个数v,u,和w输出格式:最长长度输入样例6 51 2 201 3 401 4 502 5 103 6 10输出样例100分析：认真审题，其实此题是要在带权树上求最长链，一棵有根树的最长链，可能出现如上图的两种情况设dep(i)表示以节点i为根的子树的最大深度。F(i)表

19、示以节点i为根的子树中，包含节点i的最长链长度我们有:dep(i)=maxdep(j)+w(i,j)，其中j是i的子节点F(i)=maxdep(i),dep(j)+w(i,j)+dep(k)+w(i,k)，其中j,k是i的子节点，且j<>k不难发现，我们的状态转移方程是按照从下至上的顺序计算的。做一遍DFS遍历，在回朔的时候分别计算dep和F的值,关于F值的计算：由于节点j和k之间没有关联，所以我们只需要选择两个(dep(j)+w(i,j)最大的子节点进行累加即可。 参考程序const maxn=100;var n,v,ans:integer;w:array0. maxn,0. m

20、axn of integer;dep:array1. maxn of integer;used:array1. maxn of boolean;procedure init;var i,j,x,y:integer;beginreadln(n,v);for i:=0 to n dofor j:=0 to n do wi,j:=-1;for i:=1 to v dobeginreadln(x,y,wx,y);wy,x:=wx,y;end;fillchar(used,sizeof(used),true);used1:=false; ans:=0;end;procedure dfs(x:integer

21、);/求 dep 和 f 的过程var i,max1,max2:integer;begindepx:=0; max1:=0; max2:=0;for i:=1 to n doif (wx,i<>-1)and(usedi) thenbeginusedi:=false;dfs(i);if depi+wx,i>=depx thenbegindepx:=depi+wx,i;max2:=max1;max1:=depx;endelseif depi+wx,i>max2 then max2:=depi+wx,i;end;if depx>ans then ans:=depx;if max1+max2>ans then ans:=max1+max2;end;begininit;dfs(1);writeln(ans);end.例2、ural1018二叉苹果树有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的