动态规划二动态规划二.ppt

* * 动态规划二 1、花与花瓶 　　有ｎ束花从左至右依次插在ｍ个花瓶内（１＝ｎ＝ｍ＝100）。花与瓶分别用１到ｎ与１到ｍ的整数标识。花要按照花的标识数递增排列，不同的花插在不同的瓶子里产生不同的美学价值（－５０到５０之间）。求最大的美学价值。 输入： 第一行：ｎ，ｍ。第二行到第ｎ＋１行，每行ｍ个数，是一个ｎ×ｍ的矩阵，矩阵的第ｉ行第ｊ列的数表示标识为ｉ的花插在标识为ｊ的花瓶中产生的美学价值。 输出： 一行：把ｎ束花插在ｍ个花瓶中，产生的最大美学价值。 样例： 输入： 3 5 7 　23　 -5　 -24　 16 5 　21 -4 　10 　23 -21 5 　-4 　-20 20 输出： 53 分析： 方法一：flower11.txt 　　A[i,j]=花i放入j瓶的美学价值。 　　F[i，j]=前i束花放入前j个花瓶内的最大美学价值（花i不一定必须插在瓶j内）。 计算F[I,j]有两种情况： 1): 花i放入第j个花瓶中： 　　　　 F[i，j]= f[i-1,j-1]+a[i,j] 2): 花i不放入第j个花瓶中,只能放在前j-1个花瓶内： 　　　　 F[i，j]= f[i,j-1] 动态转移方程： 　　F[i，j]＝max｛f[i-1,j-1]+a[i,j]，f[i,j-1]｝ 初始化：f[0,0]=0;　f[i,0]=-9950　(1=i=n) ？ 目标：　f[n,m] function max(a,b:integer):integer; begin if ab then max:=a else max:=b;end; procedure work; begin fillchar(f,sizeof(f),0); for i:=1 to n do f[i,0]:=-9950; {第０列表示不能插花} for i:=1 to n do {枚举每一行：花的数量} for j:=1 to m do {枚举列：花瓶的数量} f[i,j]:=max(f[i,j-1],f[i-1,j-1] +a[i,j]); end; 时间：n*m 优化： procedure work; begin fillchar(f,sizeof(f),0); for i:=1 to n do f[i,i-1]:=-9950; for i:=1 to n do {枚举花} for j:=i to i+m-n do {枚举第i束花可放的花瓶范围i} f[i,j]:=max(f[i,j-1],f[i-1,j-1]+a[i,j]); end; 时间：n*(m-n) 分析： 方法二： a,f:array[0..maxn,0..maxm]of integer; a[i,j]表示第i束花插到第j个花瓶中的价值； f[i,j]表示第i束花插到第j个花瓶后，也就是说：第i束花插在第ｊ个花瓶，前i-1束花插在前ｊ-１个花瓶内所获得的价值和的最大值。 动态转移方程： 　　f[i,j]＝max{f[i-1,k] }+ a[i,j] (i-1=k=j-1) 枚举第i-1束花所在的花瓶k 初始化：f[0,0]=0;　f[i,0]=-9950　(1=i=n) 目标：max{f[n,i]} (1=i=m) 2、制作唱片 　　你刚刚继承了ｎ首珍贵的、没有发行的歌曲，它们由流行的演唱组Ｒａｕｃｏｕｓ　Ｒｏｃｋｅｒｓ录制。你的计划是选择其中一些歌曲来发行ｍ个唱片，每个唱片至多包含ｔ分钟的音乐，唱片中的歌曲之间不能重复。 由于你是一个古典音乐的爱好者，所以你没办法区分这些歌曲的价值，你按照下面的标准作选择： 1) 这些唱片中的歌曲必须按它们写作的顺序排序。（如果第一个唱片录制了歌曲１、３，则第二个唱片只能从４开始选择） 2)包含歌曲的总数量尽可能的多。 输入：第一行包含数值ｎ，ｔ，ｍ（不大于２０的整数），下面包含ｎ首歌曲的长度，它们按写作的顺序排列，没有一首歌曲超出唱片的长度，而且不可能将所有歌曲都放在唱片中。 输出：输出应是按照标准进行选择ｍ个唱片，所能包含的最多歌曲数目。 样例： 输入： 5 6 4 4 3 4 4 5 输出： 4 算法： 　用a[i]保存第i首歌曲的长度。 　D[i,j]＝用1张盘可以保存i到j首歌曲之间最多的歌曲数目。 　设Ans[i,j]=前i首歌用j张盘可以录制的最多数量。 状态转移方程：