4种常见的动态规划模型

《4种常见的动态规划模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、=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)【问题描述】母牛们不但创

3、建了他们自己的政府而且选择了建立了自己的货币系统。他们对货币的数值感到好奇。传统地，一个货币系统是由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行:二个

4、整数，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位，为节约程序时间和空间效率，还采用了万进制的高精度加法。参考程序如下：v

5、arf: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]

6、iv10000;//每一个存4位,万进制，这样省时省空间f[t,i]:=f[t,i]mod10000;end;whilek>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位,所以有时需

7、要补零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]);mai

8、n;close(input);close(output);end.（二）、资源分配模型资源分配模型的动态规划，这类型的题目一般是：给定m个资源，分配给n个部门，第i个部门获得j个资源有个盈利值，问如何分配这m个资源能使获