当前位置:首页 >> 计算机软件及应用 >>

几个经典的动态规划问题


动态规划复习: 动态规划复习:
《便宜的旅行》分析:
这个问题很明显是一个动态规划的标准问题。 考虑某一天晚上车队到达了终点,上一次的花销必然是只与早上车队所在的位置有关 的。这样,由于要求从起点到终点最优的方案,所以从起点到达早上所出发时旅馆的方案也 应该是最优的。 以此类推, 我们可以得出我们应该求出从起点到各个旅馆的最优方案。 这样, 如果我们设从起点到旅馆 si∈S (1≤ i≤ n)的最优方案的价值为 f(si),就可以得到如下的动态规 划方程:

F(s[i])=min{f(s[j])}+value[i]; 0<=s[i]-s[j]<=800
这里 value(si)为 si 的价值。

《蛙人 蛙人》 蛙人
设 F(i,j) 是携带 i 升氧气,j 升氮气的最小重量

F(i+ak,j+tk)=min{f(i,j)+Wk}

李曙华同学程序
for i:=0 to 21 do for j:=0 to 79 do a[i,j]:=10000000; a[0,0]:=0; for i:=1 to n do begin readln(b[i,1],b[i,2],b[i,3]); for j:=21-b[i,1] downto 0 do for k:=79-b[i,2] downto 0 do begin if a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1]; if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k]; if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] then a[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3]; end; end; writeln(a[x,y]); close(input);close(output); end.

几个经典的动态规划问题

一、 背包问题:
的背包里, 在 M 件物品取出若干件放在空间为 W 的背包里,每件物品的重量为 W1, , W2……Wn,与之相对应的价值为 P1,P2……Pn。求出获得最大价值的方案。 , 。求出获得最大价值的方案。 注意:在本题中,所有的重量值均为整数。 注意:在本题中,所有的重量值均为整数。

考虑用动态规划的方法来解决,这里的: 阶段是: 件物品中,选取若干件物品放入背包中; 阶段是:在前 n 件物品中,选取若干件物品放入背包中; 状态是: 件物品中, 状态是:在前 n 件物品中,选取若干件物品放入所剩空间为 w 的背包中的所能获得的最大 价值; 价值; 决策是: 件物品放或者不放; 决策是:第 n 件物品放或者不放; 由此可以写出动态转移方程: 我们用 f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价 值

f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}
这样,我们可以自底向上地得出在前 m 件物品中取出若干件放进背包能获得的最大价值, 也就是 f[m,w] 算法设计如下: procedure make; begin for i:=0 to w do f[0,i]:=0; for i:=1 to m do for j:=0 to w do begin f[i,j]:=f[i-1,j]; if (j>=w[i]) and (f[i-1,j-w[i]]+v[i]>f[i,j]) then f[i,j]:=f[i-1,j-w[i]]+v[i]; end; writeln(f[m,wt]); end; 二、最小代价字母树--石子归并问题 石子归并问题 石子归并 石子归并是最小代价子母树的一个应用。 石子归并的问题描述: 有 n 堆石子,都有各自的重量。只能合并相邻的两堆,合并一次两堆的重量之和为这次合 并的代价。如: n=4,

13 如图:

7

14

6

f[1,4]=min{f[1,3],f[1,2]+f[3,4],f[2,4]}+40; f[1,3]=min{f[1,2],f[2,3]}+34; f[1,2]=20; f[2,3]=21; f[3,4]=20; f[2,4]=min{f[2,3],f[3,4]}+27; 引入记号:g[i,j]表示从 i 到 j 堆沙子的重量之和。 一般的: f[1,n]=min{f[1,n-1],f[1,2]+f[3,n],f[1,3]+f[4,n],...,f[2,n]}+g[1,n]

F[i,j]=min{f[i,k]+f[k+1,j]}+W[i,j] (1<=i<=k<=j) F[i,i]=0

可以先计算合并两堆的,在计算 3 堆的,依此类推。代码如下: program stone1; const max=10; var g:array[0..max,0..max] of integer; f:array[1..max,1..max] of integer; s:array[1..max] of integer;

i,j,k:integer; n,min:integer; begin assign(input,'stone.txt'); reset(input); readln(n); for i:=1 to n do read(s[i]); close(input); fillchar(g,sizeof(g),0); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=i to n do g[i,j]:=g[i,j-1]+s[j]; for i:=2 to n do for j:=1 to n-i+1 do begin min:=30000; for k:=j to j+i-2 do if min>f[j,k]+f[k+1,j+i-1] then min:=f[j,k]+f[k+1,j+i-1]; f[j,j+i-1]:=min+g[j,j+i-1]; end; writeln(f[1,n]); end.

三、最长不上升链(不下降链) 最长不下降序列(HNOI’97) 一、问题描述 设有整数 序 列 b1,b2,b3,…,bm,若 存在 i1<i2<i3<…<in, 且 bi1<bi2<bi3<…<bin,则称 b1,b2,b3,…,bm 中有长度为 n 的不下降序列 bi1,bi2,bi3,…,bin。求序列 b1,b2,b3,…,bm 中所有

长度(n)最大不下降子序列 输入:整数序列 输出:最大长度 n 和所有长度为 n 的序列个数 Total 二、分析 此题分为两个部分:求最大不下降序列长度和序列个数。 首先我们考虑求最大长度。设 F(i)为前 I 个数中的最大不下降序列长度。由题意不难得知, 要求 F(i),需要求得 F(1)—F(I-1),然后选择一个最大的 F(j) ( j<I, bi>bj ),那么前 I 个数中最 大不下降序列便是前 j 个数中最大不下降序列后添加 bi 而得。可见此任务满足最优子结构, 可以用动态规划解决。 通过上面的分析可得状态转移方程如下:

F(i)=max{F(j)+1}(j<I , bj<bi)
边界为 F(1)=1 显然只需要求序列个数即可。很容易想到下面的方法: 设 Total(I)为前 I 个数中最长不下降序列的个数。 那么,要求 Total(i),只需找到所有的 Total(j)满足 j<I,bj<bi 且前 j 个数最大不下降序列长 度为前 I 个数中最大不下降序列长度+1,并把他们累加起来。即 Total(i)=∑Total(j) (j<I, bj<bi, F(i)=F(j)-1) 在求所有的 Total(i)(F(i)=max)的累加和即可。 但这样考虑有一个致命的错误,如 122 这样一个序列,最大不下降序列长度为 2。但如果按上述方法计算序列 1 2 会算两次。因 此,我们对算法进行改进: 对原序列按 b 从小到大(当 bi=bj 时按 F 从大到小)排序,增设 Order(i)记录新序列中的 I 个 数 在 原 序 列 中 的 位 置 。 可 见 , 当 求 Total(i) 时 , 当 F(j)=F(j+1) , b(j)=b(j+1) 且 Order(j+1)<Order(i)时,便不累加 Total(j)。这样就避免了重复。 综合看来,上述算法的时间复杂度为 O(n^2),空间复杂度为 O(n),都是可行的。 三、参考程序 {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+} {$M 65520,0,655360} Program HNOI97_1; const finp ='input.txt'; fout ='output.txt'; maxN =1000; var n,len :integer; {len 记录最大长度} tot :longint; {tot 记录序列个数} f,b :array[1..maxN]of integer; Procedure init; {输入} var f :text; begin assign(f,finp);reset(f); n:=0; while not eoln(f) do begin

inc(n); read(f,b[n]) end; close(f) end; Procedure main; var i,j,t :integer; order :array[1..maxN]of integer; total :array[1..maxN]of longint; begin f[1]:=1;len:=1; {求解最大不下降序列长度} for i:=2 to n do begin f[i]:=1; for j:=1 to i-1 do if (b[i]>b[j])and(f[i]<f[j]+1) then f[i]:=f[j]+1; if f[i]>len then len:=f[i] {记录最大值} end; for i:=1 to n do order[i]:=i; for i:=1 to n do {排序} for j:=i+1 to n do if (b[i]>b[j])or(b[i]=b[j])and(f[i]>f[j]) then begin t:=b[i];b[i]:=b[j];b[j]:=t; t:=f[i];f[i]:=f[j];f[j]:=t; t:=order[i];order[i]:=order[j];order[j]:=t end; tot:=0; {计算序列个数} fillchar(total,sizeof(total),0); for i:=1 to n do begin if f[i]=1 then total[i]:=1 else for j:=i-1 downto 1 do if (f[j]=f[i]-1)and(b[j]<b[i])and(order[j]<order[i]) then if (b[j+1]<>b[j])or(f[j+1]<>f[j])or(order[j+1]>=order[i]) then inc(total[i],total[j]); if (f[i]=len)and(b[i]<>b[i+1]) then {记录累加最终值} tot:=tot+total[i] end; end; Procedure out; {输出} begin assign(output,fout);rewrite(output); writeln(len); writeln(tot);

close(output) end; Begin init; main; out End.

四、 最长公共子串
[问题描述] 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 确切地 说,若给定序列 X=<x1,x2,……,xm>,则另一序列 Z=<z1,z2,……,zk>是 X 的子序列是指存在 一个严格递增的下标序列 <i1,i2,……,ik>,使得对于所有 j=1,2,……,k 有:

例如,序列 Z=<B,C,D,B>是序列 X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为 <2,3,5,7>。给定两个序列 X 和 Y,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z 是序列 X 和 Y 的公共子序列。例如,若 X=<A,B,C,B,D,A,B>和 Y=<B,D,C,A,B,A>,则序列 <B,C,A>是 X 和 Y 的一个公共子序列,序列<B,C,B,A>也是 X 和 Y 的一个公共子序列。而且, 后者是 X 和 Y 的一个最长公共子序列,因为 X 和 Y 没有长度大于 4 的公共子序列。 给定两个序列 X=<x1,x2,……,xm>和 Y=<y1,y2,……,yn>,要求找出 X 和 Y 的一个最长公 共子序列。 [输入] 输入文件共有两行, 每行为一个由大写字母构成的长度不超过 200 的字符串, 表示序列 X 和 Y。 [输出] 输出文件第一行为一个非负整数, 表示所求得的最长公共子序列的长度, 若不存在公共 子序列,则输出文件仅有一行输出一个整数 0,否则在输出文件的第二行输出所求得的最长 公共子序列(也用一个大写字母组成的字符串表示),若符合条件的最长公共子序列不止一 个,只需输出其中任意的一个。 [输入样例] LCS.IN ABCBDAB BDCABA [输出样例] LCS.OUT 4 BCBA [评分标准] 若输出的最长公共子序列的长度正确,则得 5 分;若输出的最长公共子序 列也正确,则再得 5 分。 最长公共子序列问题也有最优子结构性质,因为我们有如下定理: 定理: LCS 的最优子结构性质 设序列 X=<x1, x2,……, xm>和 Y=<y1, y2, ……,yn>的一个最长公共子序列 Z=<z1, z2,……, zk>,则:

若 xm=yn,则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列; 若 xm≠yn 且 zk≠xm ,则 Z 是 Xm-1 和 Y 的最长公共子序列; 若 xm≠yn 且 zk≠yn ,则 Z 是 X 和 Yn-1 的最长公共子序列。 其中 Xm-1=<x1,x2,……,xm-1>,Yn-1=<y1,y2,……,yn-1>,Zk-1=<z1,z2,……,zk-1>。 这个定理告诉我们, 两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子 序列。因此,最长公共子序列问题具有最优子结构性质。 由定理可建立递归关系如下:

[参考程序] Program p8_2(Input, Output); const maxlen=200; var i,j:longint; c:array[0..maxlen,0..maxlen] of byte; x,y,z:string; begin assign(input,'lcs.in'); reset(input); readln(x); readln(y); close(input); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if x[i]=y[j] then c[i,j]:=c[i-1,j-1]+1 else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j] else c[i,j]:=c[i,j-1]; z:=''; i:=length(x); j:=length(y); assign(output,'lcs.out'); rewrite(output); writeln(c[i,j]); while (i>0) and (j>0) do if x[i]=y[j] then begin z:=x[i]+z;i:=i-1;j:=j-1 end else if c[i-1,j]>c[i,j-1]

then i:=i-1 else j:=j-1; if z<>'' then writeln(z); close(output) end.


赞助商链接
相关文章:
动态规划阶段总结之基础篇[必看]
这里基础 篇从几个例题出发, 向大家介绍几个动态规划中几种常见常用的模型,并...为一个基元更复杂一点的就是二维的串模型,例如经典的 LCS 问题(最长公共序列...
动态规划讲解大全(含例题及答案)
2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段 数就可能不同.描述阶段的变量称为阶段变量。在...
经典的动态规划入门练习题
经典的动态规划入门练习题_工学_高等教育_教育专区。动态规划入门练习题 1.石子...几个经典的动态规划问题 10页 1下载券 动态规划经典题目 38页 1下载券 动态规...
★经典动态规划收集
常见经典问题转移方程和背包红叶整理 红叶整理 2009.11 1.资源问题 1.资源问题...线性动态规划 ---最少单词个数 f[i,j]:=max{f[I,j],f[u-1,j-1]+...
动态规划
一般来说,一个经典的动态规划算法时自底向上的(从较小问题的解,由交叠性质,...再看动态规划: 上面棕色字体标出的就是一个动态规划算法的几个关键点: 1)...
经典算法——动态规划教程
动态规划经典问题 70页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...如果原问 题可以分解成几个本质相同、 规模较小的问题, 很自然就会联想到从...
动态规划36讲
动态规划(朱全民) 60页 免费 动态规划经典问题 70页 1财富值 spfa讲义+前向星...(SN) 下面看几个例题: 例题 5 装箱问题 (pack.pas/c/cpp) 来源:NOIP2001...
※动态规划经典教程
动态规划经典教程 Directory 1.1 下降/非降子序列问题: 例题 1 拦截导弹例题...(SN) 下面看几个例题: 例题 5 装箱问题 (pack.pas/c/cpp) 来源:NOIP2001...
动态规划入门(论文)
例 1:求 A—>B 的最短路径 图1 这是一个利用动态规划思想的经典问题, ...一个动态规划模型应该满足以下几个性质: 1.最优子结构性质 最优子结构可这样...
动态规划_图文
广的问题求解方法, 与分治法类似, 动态规划也是将一个问题分 解成几个问题...问题: Problem Description 在讲述 DP 算法的时候,一个经典的例子就是数塔问题...
更多相关标签: