当前位置:首页 >> 学科竞赛 >>

pascal 语言之动态规划1


pascal 语言之动态规划篇(一) ------数塔问题

数塔问题描述
如图所示数塔,从顶部出发,在每一结点可以选择向 左走或是向右走,一起走到底层,要求找出一条路径,使 路径上的值最大(IOI 94)
13
11 8

12

7 15

26

/>6

14

8

12

7

13

24

11

数塔问题求解方法探讨
采用贪心算法
图示:
11 13

13

11

12

14

13

8

12

7 15

26

所得结果并非最优路径
6
14 8

12

7

13

24

11

数塔问题求解方法探讨
采用穷举算法
基本思路:从所有可能的路径中 找出一条最优路径
11 13

8

以本题为参考,可能存在 的路径是:1×2×2×2×2 即路径总数为2N-1! 当N较大时,是一个无法 完成的运算

12

7 15

26

6

14

8

不可取

12

7

13

24

11

数塔问题求解方法探讨
采用动态规划算法
基本思路:划分阶段,自顶向下 分析,自底部向上计算。
11 13

8

解决该类问题的最优算法选择

12

7 15

26

6

14

8

为什么?
12 7 13 24

11

数塔问题动态规划求解法
动态规划算法过程描述
1、阶段划分 第五阶段 第四阶段
11 13

8

第三阶段

12

7 15

26

第二阶段 第一阶段

6

14

8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法过程描述
2、分阶段决策 第五阶段 第四阶段
11 57 86 13

8 73

第三阶段

30 12

46 7

65 26

第二阶段 第一阶段

6 18

14 27

15 39

32 8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法过程描述
3、根据最优值确定路径 第五阶段
11 57 13 86

第四阶段

73 8

第三阶段

12 30

46 7

26 65

第二阶段 第一阶段

18 6

14 27

15 39

32 8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法程序设计
图形转化
由于直角三角形便于搜索 向上、向右,故先将原图形 变为直角三角形形态 数据存储及变量设定 Var a:array[1..50,1..50,1..3] of longint; x,y,n:integer; { 1)n 表示数塔层数 2)x,y用以标示行与列 3)a[x,y,1] 数组用于读入存储初始 数据; a[x,y,2] 为状态变化数组; a[x,y,3]}为路径记录数组。}
13

11

8

12

7

26

6

14

15

8

12

7

13

24

11

数塔问题动态规划求解法
对应数组值变过程
86 13

1表示路标向右

a[x,y,2]

1 0

a[x,y,3]

57 11

73 8

1 0

1 0
0表示路标向下

39 12

46 7

65 26

1 0

1 0

0

18 6

27 14

39 15

32 8

0

1 0

1 0

0

12

7

13

24

11

0

0

0

0

0

数塔问题动态规划求解法
自顶向下的路径追溯
13

初始化行坐标x=1,列坐标y=1

X=1,y=1 ,A[x,y,1] (13),y=y+1
1

11

8

X=2,y=2 A[x,y,1] (8),y=y+1
1 1

12

7

26

1

1

0

X=3,y=3 A[x,y,1] (26),y=y+0

6

14

15

8

0

1

1

0

X=4,y=3 A[x,y,1] (15),y=y+1

12

7

13

24

11

0

0

0

0

0

X=5,y=4 A[x,y,1] (24),y=y+0

数塔问题动态规划程序参考
program shuta1; var a:array[1..50,1..50,1..3] of longint; x,y,n:integer; begin readln(n); for x:=1 to n do for y:=1 to x do begin read(a[x,y,1]); a[x,y,2]:=a[x,y,1]; a[x,y,3]:=0; end; for x:=n-1 downto 1 do for y:=1 to x do if a[x+1,y,2]>a[x+1,y+1,2] then begin a[x,y,2]:=a[x,y,2]+a[x+1,y,2]; a[x,y,3]:=0; end else begin a[x,y,2]:=a[x,y,2]+a[x+1,y+1,2]; a[x,y,3]:=1; end; writeln('max=',a[1,1,2]); y:=1; for x:=1 to n-1 do begin write(a[x,y,1],'-->'); y:=y+a[x,y,3] end; writeln(a[n,y,1]); End.

数塔问题动态规划求解法
如果该类数塔问题仅仅是为了最优解,则 状态划分可以自上而下进行。
13 13

第一阶段
8

11

第二阶段

24 11

21 8

36 12 12

7

26

第三阶段
8

31 7

47 26

6

14

15

第四阶段

42 6

50 14

62 15

55 8

12

7

13

24

11

第五阶段

54 12

57 7

75 13

86 24

66 11

数塔问题动态规划程序参考

program dtghst; var a,b:array[0..100,0..100] of longint; i,j,n:integer; max:longint; begin readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do for j:=1 to i do read(a[i,j]); b:=a; b[1,1]:=a[1,1];

for i:=2 to n do for j:=1 to i do if b[i-1,j-1]>b[i-1,j] then b[i,j]:=b[i-1,j-1]+b[i,j] else b[i,j]:=b[i-1,j]+b[i,j]; max:=0; for i:=1 to n do if b[n,i]>max then max:=b[n,i]; writeln('max=',max); end.

动态规划求解问题方法

1.确定阶段和阶段变量 阶段:过程的划分,包括时间、空间的划分, 阶段数:n 阶段变量:描述阶段的变量用k 表示,k=1,2,…..,n 2.确定状态和状态变量 状态:描述过程的必要信息。 状态应具有无后效性: 若给定了某阶段状态,则在这阶 段以后过程的发展不受这阶段以前各阶段状态的影响.

动态规划求解问题方法

3.设定决策变量进行目标决策 决策:决定(选择),从一个阶段的状态到 下一个阶段状态的选择。 决策变量:描述决策的变量,

4.选择适当的策略,形成顺序序列。
5.构造状态转移方程,使得状态沿着序列方向发展。 6.确定最终指标或最优值。

动态规划求解问题的类型

1、最优调度 2、资源分配 3、最优路径 4、最优控制 5、设备更新 6、库存问题 7、背包问题 等等……


相关文章:
动态规划教程——pascal语言描述
动态规划教程——pascal语言描述_数学_自然科学_专业资料。动态规划教程——pascal...显然对于第 i 个数时只考 虑前 i-1 个数,显然满足无后效性,可以用动态...
pascal教程8--动态规划
第八章 8.1 动态规划 字串距离源程序名 可执行文件名 输入文件名 输出文件名...noip_pascal语言_动态规... 142页 免费 Pascal动态规划 22页 免费 动态规划经典...
动态规划PASCAL
1.2 动态规划的概念 的状态中产生出来的,故有“动态”的含义,称这 begin 1...noip_pascal语言_动态规... 142页 免费 第10章 动态规划 76页 免费 动态规划...
Pascal动态规划模型一
1页 免费 Pascal动态规划 22页 免费 noip pascal语言 动态规划 142页 8财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行...
Pascal动态规划 模型二
同系列文档 Pascal动态规划模型一1/2 相关文档推荐 Pascal 动态规划 模型三 2...Pascal动态规划 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题...
pascal教程9--数学问题
关键词:pascal语言教材 1/3 同系列文档 朝鲜历届领导人资料 朝鲜现状 为什么南北...pascal教程8--动态规划 16页 20财富值 pascal教程1--回溯法 24页 20财富值 ...
动态规划第一部分
关键词:pascal语言 1/2 相关文档推荐 动态规划 32页 1财富值 动态规划 31页 免费 动态规划 32页 免费 动态规划(完整) 104页 5财富值 第八章 动态规划 23页...
Pascal 动态规划 模型三
动态规划PASCAL 5页 1下载券P​a​s​c​a​l​ ​动​态​规​划​ ​模​型​三 暂无评价|0人阅读|0次下载|举报文档今日...
动态规划——车队过桥
pascal语言pascal语言隐藏>> 动态规划-车队过桥 动态规划〖题目描述〗 GDOI 工作...大小:22.50KB 所需财富值:1 加入阅读会员!获取下载券 登录百度文库,专享文档...
PASCAL复习1
Pascal动态规划-复习2 29页 1下载券P​A​S​C​A​L​复​习...C,D,E 和 F 六种食品,单价分别为:3.1,1.7,2,5.3, 0.9 和 7.2 元...
更多相关标签:
pascal动态规划 | c语言动态规划 | 动态规划c语言代码 | 01背包动态规划c语言 | pascal语言 | pascal语言程序设计 | pascal语言教程 | pascal语言视频教程 |