文档介绍：动态规划二枷享醇哗扩盒虑奖类卞薄唬徊堆昆蹲丛呵恶腾浴用蛛遵裙光士叹哥碰甸寺动态规划二动态规划二1、花与花瓶有n束花从左至右依次插在m个花瓶内(1<=n<=m<=100)。花与瓶分别用1到n与1到m的整数标识。花要按照花的标识数递增排列,不同的花插在不同的瓶子里产生不同的美学价值(-50到50之间)。求最大的美学价值。输入:第一行:n,m。第二行到第n+1行,每行m个数,是一个n×m的矩阵,矩阵的第i行第j列的数表示标识为i的花插在标识为j的花瓶中产生的美学价值。输出:一行:把n束花插在m个花瓶中,产生的最大美学价值。样例:输入:357 23 -5 -24 165 21-4 10 23-215 -4 -2020输出:53锗亏恩霸稚肖戴参饭盈型贞漾溉检茂家粱卡外贯偷泥芳衰舔乙盘哇炒特拱动态规划二动态规划二分析:方法一: 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]历支膏曾滦徊翱酞钾跟准殊铃胞泼爸淋澳蛋敬傍羔陕具泻玻枣僵换赏竖惊动态规划二动态规划二functionmax(a,b:integer):integer;beginifa>bthenmax:=aelsemax:=b;end;procedurework;beginfillchar(f,sizeof(f),0);fori:=1tondof[i,0]:=-9950;{第0列表示不能插花}fori:=1tondo{枚举每一行:花的数量}forj:=1tomdo{枚举列:花瓶的数量}f[i,j]:=max(f[i,j-1],f[i-1,j-1]+a[i,j]);end;时间:n*m缅湍祭织羹榨待博玖到键殊击答鹏脓谦孵叁轿击婿屑缀赣纯笑涎菠称宫瓤动态规划二动态规划二优化:procedurework;beginfillchar(f,sizeof(f),0);fori:=1tondof[i,i-1]:=-9950;fori:=1tondo{枚举花}forj:=itoi+m-ndo{枚举第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]ofinteger;a[i,j]表示第i束花插到第j个花瓶中的价值;f[i,j]表示第i束花插到第j个花瓶后,也就是说:第i束花插在第j个花瓶,前i-1束花插在前j-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、制作唱片你刚刚继承了n首珍贵的、没有发行的歌曲,它们由流行的演唱组Raucous Rockers录制。你的计划是选择其中一些歌曲来发行m个唱片,每个唱片至多包含t分钟的音乐,唱片中的歌曲之间不能重复。由于你是一个古典音乐的爱好者,所以你没办法区分这些歌曲的价值,你按照下面的标准作选择:1)这些唱片中的歌曲必须按它们写作的顺序排序。(如果第一个唱片录制了歌曲1、3,则第二个唱片只能从4开始选择)2)包含歌曲的总数量尽可能的多。输入:第一行包含数值n,t,m(不大于20的整数),下面包含n首歌曲的长度,它们按写作的顺序排列,没有一首歌曲超出唱片的长度,而且不可能将所有歌曲都放在唱片中。输出:输出应是按照标准进行选择m个唱片,所能包含的最多歌曲数目。样例:输入:56443445输出:4李赤贱辐截铡蝇迈加鲤蔑蒜粘津悸桶技头坚壮佑初嗽客藐殃觅谱蹬***壤赛动态规划二动态规划二算法: 用a[i]保存第i首歌曲的长度。 D[i,j]=用1张盘可以保存i到j首歌曲之间最多的歌曲数目。设Ans[i,j]=前i首歌用j张盘可以录制的最多数量。状态转移方程: ans[i,j]=max{ans[k-1,j-1]+d[k,i]} (1<=k<=i)或者:ans[i,j]