动态程序设计(重点)

《动态程序设计(重点)》由会员分享，可在线阅读，更多相关《动态程序设计(重点)（71页珍藏版）》请在金锄头文库上搜索。

1、动态程序设计王忠厚基本原理1、多阶段最优化决策：即由初始状态开始，通过对中间阶 段决策的选择，达到结束状态。这些决策形成了一个决策 序列，同时确定了完成整个过程的一条最优的活动路线。带权有向的多段图 上一阶段的状态下一阶段的状态决策概念w 状态（State）：表示事物的性质，是描述“动态规划”中的“单元 ”的量。亦是每一阶段求解过程的出发点。 w 阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集 合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的 状态。 w 决策（Decision）：每个阶段做出的某种选择性的行动，是程 序所需要完成的选择。 w 状态转移方程：是前一个阶段的

2、状态转移到后一个的状态的演 变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的 中心。设fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价fk+1(i)=minxk(j)+u(i,j) 基本原理w 最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的 状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶 段以前各段状态的影响，所有各阶段都确定时，整个过程也就确 定了。这个性质意味着过程的历史只能通过当前的状态去影响它 的未来的发展，这个性质称为无后效性。机器分配 w 总公司拥有高效生产设备M台，准备分给下

3、属的N个公 司。各分公司若获得这些设备，可以为国家提供一定 的盈利。问：如何分配这M台设备才能使国家得到的盈 利最大？求出最大盈利值。其中M=n），x,y是上面一块积木接触面的两条边（ x=y），则一定满足m.=x和n=y； w 下面的积木的编号要小于上面的积木的编号。 w 请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子 的高度之和最大。积木游戏w 输入数据： w 文件的第一行是两个正整数N和M（1= M = N =100）,分别表示积木总数和要 求摞成的柱子数。这两个数之间用一个 空格符隔开。接下来的N行是编号从1到 N个积木的尺寸，每行有三个1至500之间 的整数，分别表示该积木

4、三条边的长度 。同一行相邻两个数之间用一个空格符 隔开。 w 输出数据： w 文件只有一行，是一个整数，表示所求 得的游戏方案中M根柱子的高度之和 分析w 设 （1） fi,j,k表示以第i块积木的第k面为第j根柱子的顶面的最优方案 的高度总和； （2）blocki,k 记录每个积木的三条边信息（blocki,4:=blocki,1; blocki,5:=blocki,2）。其中blocki,j+2表示当把第i块积木的第j 面朝上时所对应的高，即所增加的高度； （3）cani,k,p,kc表示第I块积木以其第k面朝上，第p块积木以第kc面 朝上时，能否将积木I放在积木p的上面。1表示能，0表示

5、不能。 对于fi,j,k, 有两种可能：1. 除去第I块积木，第j根柱子的最上面的积木为编号为p的，若第 p块积木以第kc面朝上，必须保证当第I块积木以k面朝上时能够被 放在上面，即cani,k,p,kc=1；2. 第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为 第p块积木，则此时第p块积木可以以任意一面朝上。则有：动态规划w 边界条件： w f1,1,1:=block1,1,3; f1,1,2:=block1,1,4; f1,1,3:=block1,1,5; w fi,0,k:=0; (1= i = n, 1= k = 3); w 时间复杂度为O(n2*m) 免费馅饼 w SE

6、RKOI最新推出了一种叫做“免费馅饼”的游戏。 w 游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格 ，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着 一个托盘。 w 游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落 。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格 或两格，也可以站在愿地不动。 w 馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打 了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一 样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏 者所在的格子中，游戏者就收集到了这块馅饼。 w 写一个程序，帮助我们的游戏者收集馅饼

7、，使得收集的馅饼的分 数之和最大。免费馅饼w 输入数据：输入文件的第一行是用 空格分开的两个正整数，分别给出 了舞台的宽度W（199之间的奇数 ）和高度H（1 100之间的整数） 。 w 接下来依馅饼的初始下落时间顺序 给出了一块馅饼信息。由四个正整 数组成，分别表示了馅饼的初始下 落时刻（0 1000秒），水平位置 、下落速度（1 100）以及分值。 游戏开始时刻为0。从1开始自左向 右依次对水平方向的每格编号。 w 输出数据：输出文件的第一行给出 了一个正整数，表示你的程序所收 集到的最大分数之和。分析w 我们将问题中的馅饼信息用一个表格存储。表格的第I 行第J列表示的是游戏者在第I秒到达

8、第J列所能取得的 分值。那么问题便变成了一个类似数字三角形的问题 ：从表格的第一行开始往下走，每次只能向左或右移 动一格或两格，或不移动走到下一行。怎样走才能得 到最大的分值。 w 因此，我们很容易想到用动态规划求解。 w FI,J表示游戏进行到第I秒，这时游戏者站在第J列时 所能得到的最大分值。那么动态转移方程为：FI,J = Max FI-1,K + 馅饼的分值 ( J-2=K=J+2 )w 有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有 (n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离 都等于d，每个格子的宽度也都等于d，且除了最左端和最右端 的格子外每

9、个格子都正对着最下面一排钉子的间隙。 w 让一个直径略小于d的小球中心正对着最上面的钉子在板上自由 滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2 ），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就 是小球一条可能的路径。 w 我们知道小球落在第i个格子中的概率pi= ，其中i为 格子的编号，从左至右依次为0,1,.,n。 w 现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中 的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉 子被拔掉后小球一条可能的路径。钉子和小球 钉子和小球 w 输入：第1行为整数n（2=n=50）和m（0=m=n）。以下n行 依次为木板

10、上从上至下n行钉子的信息，每行中*表示钉子还 在，.表示钉子被拔去，注意在这n行中空格符可能出现在任何 位置。 w 输出：仅一行，是一个既约分数(0写成0/1)，为小球落在编号为 m的格子中的概率pm分析w 设三角形有n行，第i行（1=i=n）有i个铁钉位置，其编号为0i-1 ；第n+1行有n+1个铁钉位置，排成n+1个格子，编号为0n。设经 过位置（i,j）的小球个数为Pi,j，则落入格子m的小球个数为Pn+1,m ，问题要求的是Pn+1,m /2n。 w 假设位置(i,j)有铁钉，则各有Pi,j /2个小球落入位置（i+1,j）和位置 (i+1,j+1)；否则Pi,j 个小球将全部落入位置

11、(i+2,j+1)。 w 可得如下算法：P1,0 2n ; for i1 to n do for j1 to n do if 位置(i,j)有钉子 then Pi+1,j Pi+1,j + Pi,j /2 ;Pi+1,j+1 Pi+1,j+1 + Pi,j /2 ; else Pi+2,j+1 Pi+2,j+1 + Pi,j ; w 问题求的是既约分数，因为分母为2的次幂，因此可把分子、分母 同时约去2的因子，直至分子不能整除2。商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是 信息学竞赛 的货币 的单位）;一个花瓶的价格是5 ICU。为了吸引更多 的顾客，商

12、店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵 花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价 以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量 ，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定 各种商品价格用优惠价如上所述，并且某顾客购买 物品为:3朵花和2个 花瓶。那么顾客应付款为14 ICU因为:1朵花加2个花瓶: 优惠价:10 ICU2朵花 正常价: 4 ICU商店购物输入数据第一个文件INPUTTXT的格式为:第一行是一个数字B（

13、0B5 ），表示所购商品种类数。下面共B行，每行中含3个数C，K，P 。C 代表商品的编码 （每种商品有一个唯一的编码 ）， 1C999。K代表该种商品购买总 数，1K5。P 是该种商 品的正常单价（每件商品的价格），1P999。请注意，购物 筐中最多可放5*525件商品。 第二个文件OFFERTXT的格式为:第一行是一个数字S（0S99） ，表示共有S种优惠。下面共S行，每一行描述一种优惠商品的 组合中商品的种类。下面接着是几个数字对（C，K），其中C代 表商品编码 ，1C9 99。K代表该种商品在此组合中的数量 ，1K5。本行最后一个数字P（1 P9999）代表此商品组 合的优惠价。当然，

14、 优惠价要低于该组 合中商品正常价之总 和。 输出数据在输出文件OUTPUTTXT中写 一个数字（占一行）， 该数字表 示顾客所购商品（输入文件指明所购商品）应付的最低货款。 分析w 由于动态规划要满足无后效性和最优化原理，所以我们来分析此 题是否满足以上两点。首先确定状态，商品不超过5种，而每种采 购的数量又不超过5，那么用一个五元组来表示第i种商品买Ai的 最小费用。 w F（A1，A2，A3，A4，A5） （1） w 考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然 这样不是最优。于是如果我们能够使用第i条商品组合的话，状态 就b变为了： w F（A1-SI1，A2-SI2，A3

15、-SI3，A4-SI4，A5-SI5） （2） w 这样的话，状态1的费用为状态2的费用加上Si的费用，而状态2的 费用必须最低（很显然，用反证法即可），同时，我们也不管状 态2是如何来的（因为每一个优惠商品组合的使用是没有限制的） ，所以本题既满足无后效性，又符合最优化原理，同时还有大量 重叠子问题产生，动态规划解决此题是最好不过了。状态转移方程w F a, b, c, d, e = MinFa-Si1,b-Si2,c-Si3,d-Si4,e-Si5+SaleCostSi(0=i=S, 0=a, b, c, d, e=5) 初始条件为：F a, b, c, d, e = Cost1*a+Co

16、st2*b+Cost3*c+Cost4*d+Cost5*e添括号问题 w 有一个由数字1，2，. ，9组成的数字串（长度不超过200）， 问如何将M(M=20)个加号(“+“)插入到这个数字串中，使所形成 的算术表达式的值最小。请编 一个程序解决这个问题 。 w 注意： w 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以 上的加号相邻。 w M保证小于数字串的长度。 w 例如：数字串79846，若需要加入两个加号，则最佳方案为 79+8+46，算术表达式的值133。 w 输入格式 w 从键盘读入输入文件名。数字串在输入文件的第一行行首（数字 串中间无空格且不折行），的值在输入文件的第二行行首。 w 输出格式 w 在屏幕上输出所求得的最小和的精确值。分析w 考虑到数据的规模超过了长整型,我们注意在解题过程中采用