动态规划及其应用.ppt

动态规划及其应用 赖国堃 福建师大附中 基本概念 动态规划问题的满足两个基本性质 一、最优子结构 问题可以表示为一些子问题，然后通过求解子问题的最优答案，得到问题答案。 二、无后效性 当前决策不会影响到之后的决策。 动态规划的3个基本要素 状态 转移 边界 这3个一般是做动态规划时要先思考清楚的问题。 例题 例1、数字三角形 　　（图2－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 　●每一步可沿左斜线向下或右斜线向下走； 　●1＜三角形行数≤100； 　●三角形中的数字为整数0，1，…99； 输入数据： 由INPUT.TXT文件中首先读到的是三角形的行数。 在例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出数据： 把最大总和（整数）写入OUTPUT.TXT文件。 上例为： 30 　　　　　　　　　　　　　　　　 分析 只要对该题稍加分析，就可以得出一个结论： 　　如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。 　　我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。 状态：f[I,j]表示，走到第i行第j列最大得分 转移：f[I,j]=f[i-1,j-1]+c[I,j](j1) =f[I-1,j]+c[I,j](ji) For i := 2 to N Do For j := 1 to i Do Begin List[i, j].Tot := -1; { 从[1,1]至[i,j]的数字和初始化 } If (j 1) And (List[i - 1, j - 1].Tot + List[i, j].Val List[i, j].Tot) Then List[i, j].Tot := List[i - 1, j - 1].Tot + List[i, j].Val; { 若从[i-1,j-1]选择右斜线向下会使[1,1]至[i,j]的数字和最 大,则决策该步 } If (j i) And (List[i - 1, j].Tot + List[i, j].Val List[i, j].Tot) Then List[i, j].Tot := List[i - 1, j].Tot + List[i, j].Val { 若从[i-1,j]选择左斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步 } End; {for} 例题 有一个体积为V背包，现在有n个物品，他们格子有自己的体积vi，和各自的价值wi。现在需要选出一些物品装进背包，你的任务是使装进物品的价值最大。 状态：f[I,j](i表示处理第几个物品，j表示已用了多大空间) 转移：f[I,j]=max(f[i-1,j-v[i]]+c[i],f[i-1,j]) 边界：f[0,0]=0; for i:=1 to n do for j:=1 to m do begin if j=v[i] then f[i,j]:=max(f[i-1,j-v[i]]+c[i],f[i-1,j]) else f[i,j]:=f[i-1,j]; end; 例题 【问题描述】 假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V 是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F 的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I J，则花束I 必须放在花束J左边的花瓶中。??? 例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时会产生不同的美学效果，并以美学值(