种常见的动态规划模型VIP免费

例谈四种常见的动态规划模型动态规划是解决多阶段决策最优化问题的一种思想方法，本文主要结合一些例题，把一些常见的动态规划模型，进行归纳总结。（一）、背包模型可用动态规划解决的背包问题，主要有01背包和完全背包。对于背包的类型，这边就做个简单的描述：n个物品要放到一个背包里，背包有个总容量m，每个物品都有一个体积w[i]和价值v[i]，问如何装这些物品,使得背包里放的物品价值最大。这类型的题目，状态表示为：f[j]表示背包容量不超过j时能够装的最大价值，则状态转移方程为：f[j]:=max{f[j-w[i]]+v[i]},边界：f[0]:=0;简单的程序框架为：beginreadln(m,n);fori:=1tondoreadln(w[i],v[i]);f[0]:=0;fori:=1tomdoforj:=1tondobeginifi>=w[j]thent:=f[i-w[j]]+v[j];ift>f[i]thenf[i]:=t;end;writeln(f[m]);end.这类型的题目应用挺广的（noip1996提高组第4题，noip2001普及组装箱问题，noip2005普及组采药等），下面一个例子，也是背包模型的简单转化。货币系统(money)【问题描述】母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。他们对货币的数值感到好奇。传统地，一个货币系统是由1，5，10，20或25，50，100的单位面值组成的。母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。使用一个货币系统{1,2,5,10,..}产生18单位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一个确定的面值。【输入格式】货币系统中货币的种类数目是v(1≤v≤25)；要构造的面值是n(1≤n≤10,000)；第1行:二个整数，v和n；第2..v+1行：可用的货币v个整数(每行一个)。【输出格式】单独的一行包含那个可能的构造的方案数。【输入样例】310125【输出样例】10[分析]：此题是个背包模型，只是问题的解是构造方案数,设w[j]为第j种币值，状态f[i]：构造面值为i时可能的方案数，则状态转移方程为：f[i]:=∑f[i-w[j]]，i>=w[j],边界：f[0]:=1;f[n]即为问题的解。注意：由于此题的数据规模比较大，所以要用到高精度加法，估计最大的数据可以达到73位，为节约程序时间和空间效率，还采用了万进制的高精度加法。参考程序如下：varf:array[0..10000,1..20]ofinteger;long:array[0..10000]ofinteger;//存储位数w:array[0..25]ofinteger;n,m,i,j,k:integer;procedureadd(r,t:integer);//万进制高精度加vari,k:integer;beginiflong[t]0do//进位处理begininc(long[t]);f[t,long[t]]:=kmod10000;k:=kdiv10000;end;end;proceduremain;vari,j:integer;beginf[0,1]:=1;long[0]:=1;fori:=1tomdoforj:=w[i]tondoadd(j-w[i],j);write(f[n,long[n]]);//输出答案,由于每个存4位,所以有时需要补零fori:=long[n]-1downto1dobeginiff[n,i]<10thenwrite('000')elseiff[n,i]<100thenwrite('00')elseiff[n,i]<1000thenwrite('0');write(f[n,i]);end;end;beginassign(input,'money.in');reset(input);assign(output,'money.out');rewrite(output);readln(m,n);fori:=1tomdoreadln(w[i]);main;close(input);close(output);end.（二）、资源分配模型这类型的题目一般用资源数做状态，数组f[i,j]表示前个i个部门分配j个资源的最大盈利，则状态转移方程为：f[i,j]:=max{f[i-1,k]+value[i,j-k]}(0<=k<=j)程序框架如下：vari,j,k:longint;beginfori:=1tondoforj:=0tomdofork:=0tojdoiff[i-1,k]+value[i,j-k]>f[i,j]thenf[i,j]:=f[i-1,k]+value[i,j-k];writeln(f[n,m]);end;资源分配类型典型应用是花店橱窗(flower.pas)设置，没做过的同学可以自己去练习一下，下面的一个例题，也是此类型的转换。[问题描述]农夫ion放完马以后，需要把马儿关回马厩。为了做好这件事，ion让马排成一行跟着他入马厩。他想出了一个就近入厩的办法：让前p1匹马进入第一个马厩，然后的p2匹马进入第二个马厩，如此类推。而且，他不想让任何一个马厩（共k个）留空...