动态规划及其应用.ppt

《动态规划及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、动态规划及其应用赖国堃福建师大附中基本概念动态规划问题的满足两个基本性质一、最优子结构问题可以表示为一些子问题，然后通过求解子问题的最优答案，得到问题答案。二、无后效性当前决策不会影响到之后的决策。动态规划的3个基本要素状态转移边界这3个一般是做动态规划时要先思考清楚的问题。例题例1、数字三角形（图2－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。●每一步可沿左斜线向下或右斜线向下走；●1＜三角形行数≤100；●三角形中的数字为整数0，1，…99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如

2、下：5738810274445265输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30分析只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。状态：f[I,j]表示，走到第i行第j列最大得分转移：f[I

3、,j]=f[i-1,j-1]+c[I,j](j>1)=f[I-1,j]+c[I,j](j1)And(List[i-1,j-1].Tot+List[i,j].Val>List[i,j].Tot)ThenList[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+Lis

4、t[i,j].Val>List[i,j].Tot)ThenList[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;fori:=1tondoforj

5、:=1tomdobeginifj>=v[i]thenf[i,j]:=max(f[i-1,j-v[i]]+c[i],f[i-1,j])elsef[i,j]:=f[i-1,j];end;例题【问题描述】假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I

6、秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。比如杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最

7、大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤100，－50≤AIJ≤50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。【输入文件】第一行包含两个数：F，V。随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数【输出文件】包含两行:第一行是程