4_动态程序设计_朱全民

4_动态程序设计_朱全民 朱全民 基本原理 1、多阶段最优化决策即由初始状态开始通过对中间阶段决策的选择达到结束状态。这些决策形成了一个决策序列同时确定了完成整个过程的一条最优的活动路线。 带权有向的多段图 上一阶段 的状态 下一阶段 的状态 决策 概念 ?状态State表示事物的性质是描述―动态规划‖中的―单元‖的量。亦是每一阶段求解过程的出发点。 ?阶段Stage阶段是一些性质相近可以同时处理的状态集合或者说阶段只是标识那些处理方法相同、处理顺序无关的状态。 ?决策Decision每个阶段做出的某种选择性的行动是程序所需要完成的选择。 ?状态转移方程是前一个阶段的状态转移到后一个的状态的演变规律是关于两个相邻阶段状态变化的方程是―动态规划‖的中心。设 fki—k阶段状态i的最优权值即初始状态至状态i的最优代价 fk1iminxkjuij 基本原理 最优性原理 作为整个过程的最优策略它满足相对前面决策所形成的状态而言余下的子策略必然构成―最优子策略‖。 无后效性原则 给定某一阶段的状态则在这一阶段以后过程的发展不受这阶段以前各段状态的影响所有各阶段都确定时整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展这个性质称为无后效性。 机器分配 总公司拥有高效生产设备M台准备分给下属的N个公司。各分公司若获得这些设备可以为国家提供一定的盈利。问如何分配这M台设备才能使国家得到的盈利最大求出最大盈利值。其中Mlt15Nlt10。分配原则每个公司有权获得任意数目的设备但总台数不得超过总设备数M。 数据文件格式为第一行保存两个数第一个数是设备台数M第二个数是分公司数N。接下来是一个MN的矩阵表明了第I个公司分配J台机器的盈利。 分析 用机器数来做状态数组FIJ表示前I个公司分配J台机器的最大盈利。则状态转移方程为: FIJMaxFI-1K ValueIJ-K 1ltIltN1ltJltM0ltKltJ 初始值: F000 时间复杂度ONM2 最长不下降序列 设有整数序列b1b2b3…bm若存在下标i1lti2lti3lt …ltin且bi1ltbi2ltbi3lt …ltbin则称 b1b2b3…bm中有长度为n的不下降序列bi1 bi2 bi3 …bin 。 求序列b1b2b3…bm中所有长度n最大不下降子序列 输入整数序列。 输出最大长度n和所有长度为n的序列个数。 分析 1设fi为前i个数中的最大不下降序列长度 则 fimaxfj1 1ltjltiltm bjltbi 边界为F11 2设ti为前i个数中最长不下降序列的个数则 ti?tj 1ltjltiltm bjltbi fifj-1 初始为ti1 当fin时将ti累加 举例 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2 答案f7时边界为?t4 进一步 3求本质不同的最长不下降序列个数有多少个 如1 2 3 4 6 5 8 10 9 有 1 2 3 4 6 8 10 1 2 3 4 5 8 10 1 2 3 4 6 8 9 1 2 3 4 5 8 9 都是本质不同的。 但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有8个其中4个1 2 3 5 4个1 2 3 4 改进算法 上例显然对于相两个相同的数重复算了多次因此我们对算法进行改进 对原序列按b从小到大当bibj时按F从大到小排序增设Orderi 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 新序列中的i个数在原序列中的位置。可见 求ti时当fjfj1bjbj1且Orderj1ltOrderi时便不累加tj。这样就避免了重复。 上述算法的时间复杂度为On2 凸多边形三角划分 给定一个具有NNlt50个顶点从1到N编号的凸多边形每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形使得这些三角形顶点的权的乘积之和最小 输入文件第一行 顶点数N 第二行 N个顶点从1到N的权值 输出格式最小的和的值 各三角形组成的方式 输入示例5 122 123 245 231 输出示例The minimum is 12214884 The formation of 3 triangle: 3 4 5 1 5 3 1 2 3 分析 设FIJIltJ表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积我们可以得到下面的动态转移方程 FIJMinFIKFKJSISJSK 0ltIltKltJltN 初始条件:F120 目标 状态:F1N 但我们可以发现由于这里为乘积之和在输入数据较大时有可能超过长整形范围所以还需用高精度计算 系统可靠性 一个系统由若干部件串联而成只要有一个部件故障系统就不能正常运行为提高系统的可靠性每一部件都装有备用件一旦原部件故障备用件就自动进入系统。显然备用件越多系统可靠性越高但费用也越大那么在一定总费用限制下系统的最高可靠性等于多少 给定一些系统备用件的单价Ck以及当用Mk个此备用件时部件的正常工作概率PkMk总费用上限C。求系统可能的最高可靠性。 输入文件格式 第一行n C 第二行C1 P10 P11 … P1X1 0ltX1ltC/Ck … 第 n 行Cn Pn0 Pn1 … PnXn 0ltXnltC/Cn 分析 例输入2 20 3 0 .6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 输出0.6375 设FImoney表示将money的资金用到前I项备用件中去的最大可靠性则有 FImoney maxFI-1 money–kCostI PIk 0ltIltn0ltKlt money div CostI 初始 F000 目标 FnC 快餐问题 Peter最近在R市开了一家快餐店为了招揽顾客该快餐店准备推出一种套餐该套餐由A个汉堡B个薯条和C个饮料组成。价格便宜。为了提高产量Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡薯条和饮料由于每条生产线每天所能提供的生产时间是有限的、不同的而汉堡薯条和饮料的单位生产时间又不同。这使得Peter很为难不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序计算一天中套餐的最大生产量。为简单起见假设汉堡、薯条和饮料的日产量不超过100个。 输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1p2p3分别为汉堡薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N0lt0lt10第四行为N个不超过10000的正整数分别为各条生产流水线每天提供的生产时间中间以一个空格分开。 输出:每天套餐的最大产量。 分析 本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立不互相影响的所以此题可以以生产线为阶段用动态规划求解。 状态表示用pijk表示前i条生产线生产j个汉堡k个薯条的情况下最多可生产饮料的个数。 用rijk表示第i条生产线生产j个汉堡k个薯条的情况下最多可生产饮料的个数。 态转移方程 pijk Maxpi-1j1k1rij-j1k-k1 0ltj1ltjlt1000ltk1ltklt100 且j-j1p1k-k1p2ltTi---第i条生产线的生产时间 rij-j1k-k1Ti-j-j1p1k-k1p2 div p3 此算法的时间复杂度为ON1004 优化 在本题中可以在动态规划方法中加入了贪心算法思想即首先计算出每天生产套数的上限值由ABC计算即min100 div A100 div B100 div c接着用贪心法计算出这N条流水线可以生产的套数并与上限比较大于则输出上限值并退出否则再调用动态规划同时在运行动态规划的过程中也可以每完成一阶段工作便与上限值进行比较这样以来便可望在动态规划完成前提前结束程序。其算法设计为 S1读入数据。 S2贪心求上限并计算出一可行解判断是否需进行下一步。 S3动态规划求解。 S4输出。 其他优化方法 1.存储结构由于每一阶段状态只与上一阶段状态有关所以我们可以只用两个100100的数组滚动实现。但考虑到滚动是有大量的赋值可以改进为动态数组每次交换时只需交换指针即可这样比原来数组间赋值要快。 2.减少循环次数在计算每一阶段状态过程中无疑要用到4重循环我们可以这样修改每一重循环的起始值和终数其中q1q2为AB上限值。 原起始值 改进后的起始值 for i:1 to n do for i:1 to n do for j:0 to toti div p1 do for j:0 to minq1toti div p1 do for k:0 to toti-p1j div p2 do for k:0 to minq2toti-p1jdiv p2 do for j1:0 to j do for j1 : max0j-ti div p1 to minjtoti-1 div p1 do for k1 : 0 to k do for k1:max0k-ti-j-j1p1 div p2 to minktoti-1-p1j1div p2 do 石子合并 在一园形操场四周摆放N堆石子N?100现要将石子有次序地合并成一堆. 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 每次只能选相临的两堆合并成一堆并将新的一堆的石子数记为该次合并的得分。编一程序由文件读入堆数N及每堆石子数?20 1选择一种合并石子的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 使得做N-1次合并得分的总和最少 2 选择一种合并石子的方案使得做N-1次合并得分的总和最大 输入数据: 第一行为石子堆数N 第二行为每堆石子数每两个数之间用一空格分隔. 输出数据 : 从第1至第N行为得分最小的合并方案. 第N1行为空行.从N2到2N1行是得分最大的合并方案. 示例 贪心法 N5 石子数分别为3 4 6 5 4 2。 用贪心法的合并过程如下 第一次 3 4 6 5 4 2得分 5 第二次 5 4 6 5 4得分9 第三次 9 6 5 4得分9 第四次 9 6 9得分15 第五次 15 9得分24 第六次24 总分62 然而仔细琢磨后发现更好的方案 第一次3 4 6 5 4 2得分 7 第二次7 6 5 4 2得分13 第三次13 5 4 2得分6 第四次13 5 6得分11 第五次 13 11得分24 第六次24 总分61 显然贪心法是错误的。 动态规划 用dataij表示将从第i颗石子开始的接下来j颗石子合并所得的分值 maxij表示将从第i颗石子开始的接下来j颗石子合并可能的最大值那么 maxij maxmaxi k maxi k j – k dataik dataik j–k 2ltkltj maxi1 0 同样的我们用minij表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值可以得到类似的方程 minij minmini k mini k j – k dataik dataik j– k 0ltkltj mini0 0 这样我们完美地解决了这道题。时间复杂度也是On2。 积木游戏 一种积木游戏游戏者有N块编号依次为12…N的长方体积木。第I块积木通过同一顶点三条边的长度分别为aibicii12…N1 从N块积木中选出若干块并将他们摞成M1lt M lt N根柱子编号依次为12…M要求第k根柱子的任意一块积木的编号都必须大于第K-1根柱子任意一块积木的编号2ltKltM。 2 对于每一根柱子一定要满足下面三个条件 除最顶上的一块积木外任意一块积木的上表面同且仅同另一块积木的下表面接触 对于任意两块上下表面相接触的积木若mn是下面一块积木接触面的两条边mgtnxy是上面一块积木接触面的两条边xgty则一定满足m.gtx和ngty 下面的积木的编号要小于上面的积木的编号。 请你编一程序寻找一种游戏方案使得所有能摞成的M根柱子的高度之和最大。 积木游戏 输入数据 文件的第一行是两个正整数N和M1lt M lt N lt100分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来的N行是编号从1到N个积木的尺寸每行有三个1至500之间的整数分别表示该积木三条边的长度。同一行相邻两个数之间用一个空格符隔开。 输出数据 文件只有一行是一个整数表示所求得的游戏方案中M根柱子的高度之和 分析 设 1 fijk表示以第i块积木的第k面为第j根柱子的顶面的最优方案的高度总和 2blockik 记录每个积木的三条边信息blocki4:blocki1 blocki5:blocki2。其中blockij2表示当把第i块积木的第j面朝上时所对应的高即所增加的高度 3canikpkc表示第I块积木以其第k面朝上第p块积木以第kc面朝上时能否将积木I放在积木p的上面。1表示能0表示不能。对于fijk 有两种可能 1. 除去第I块积木第j根柱子的最上面的积木为编号为p的若第p块积木以第kc面朝上必须保证当第I块积木以k面朝上时能够被放在上面即canikpkc1 2. 第i块积木是第j根柱子的第一块积木第j-1根柱子的最上面为第p块积木则此时第p块积木可以以任意一面朝上。则有 动态规划 311121max131112maxmaxkcipjiblockkcjpfkcpkicankcipjiblockkcjpfkjif且边界条件 f111:block113 f112:block114 f113:block115 fi0k:0 1lt i lt n 1lt k lt 3 时间复杂度为On2m 免费馅饼 SERKOI最新推出了一种叫做―免费馅饼‖的游戏。 游戏在一个舞台上进行。舞台的宽度为W格天幕的高度为H格游戏者占一格。开始时游戏者站在舞 台的正中央手里拿着一个托盘。 游戏开始后从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格也可以站在愿地不动。 馅饼有很多种游戏者事先根据自己的口味对各种馅饼依次打了分。同时在8-308电脑的遥控下各种馅饼下落的速度也是不一样的下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中游戏者就收集到了这块馅饼。 写一个程序帮助我们的游戏者收集馅饼使得收集的馅饼的分数之和最大。 免费馅饼 输入数据输入文件的第一行是用空格分开的两个正整数分别给出了舞台的宽度W199之间的奇数和高度H1 100之间的整数。 接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成分别表示了馅饼的初始下落时刻0 1000秒水平位置、下落速度1 100以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。 输出数据输出文件的第一行给出了一个正整数表示你的程序所收集到的最大分数之和。 分析 我们将问题中的馅饼信息用一个表格存储。表格的第I行第J列表示的是游戏者在第I秒到达第J列所能取得的分值。那么问题便变成了一个类似数字三角形的问题从表格的第一行开始往下走每次只能向左或右移动一格或两格或不移动走到下一行。怎样走才能得到最大的分值。 因此我们很容易想到用动态规划求解。 FIJ表示游戏进行到第I秒这时游戏者站在第J列时所能得到的最大分值。那么动态转移方程为 FIJ Max FI-1K 馅饼的分值 J-2ltKltJ2 商店购物 某商店中每种商品都有一个价格。例如一朵花的价格是2 ICUICU 是信息学竞赛的货币的单位一个花瓶的价格是5 ICU。为了吸引更多的顾客商店提供了特殊优惠价。 特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU 2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意你不能变更顾客所购商品的种类及数量即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为: 1朵花加2个花瓶: 优惠价:10 ICU 2朵花 正常价: 4 ICU 商店购物 输入数据 第一个文件INPUTTXT的格式为:第一行是一个数字B0?B?5表示所购商品种类数。下面共B行每行中含3个数CKP。C 代表商品的编码每种商品有一个唯一的编码1?C?999。K代表该种商品购买总数1?K?5。P 是该种商品的正常单价每件商品的价格1?P?999。请注意购物筐中最多可放5525件商品。 第二个文件OFFERTXT的格式为:第一行是一个数字S0?S?99表示共有S种优惠。下面共S行每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对CK其中C代表商品编码1?C?9 99。K代表该种商品在此组合中的数量1?K?5。本行最后一个数字P1? P?9999代表此商品组合的优惠价。当然 优惠价要低于该组合中商品正常价之总和。 输出数据 在输出文件OUTPUTTXT中写 一个数字占一行 该数字表示顾客所购商品输入文件指明所购商品应付的最低货款。 分析 由于动态规划要满足无后效性和最优化原理所以我们来分析此题是否满足以上两点。首先确定状态商品不超过5种而每种采购的数量又不超过5那么用一个五元组来表示第i种商品买Ai的最小费用。 FA1A2A3A4A5 1 考虑这个状态的由来当然我们不用优惠商品也可以买显然这样不是最优。于是如果我们能够使用第i条商品组合的话状态就b变为了 FA1-SI1A2-SI2A3-SI3A4-SI4A5-SI5 2 这样的话状态1的费用为状态2的费用加上Si的费用而状态2的费用必须最低很显然用反证法即可同时我们也不管状态2是如何来 的因为每一个优惠商品组合的使用是没有限制的所以本题既满足无后效性又符合最优化原理同时还有大量重叠子问题产生动态规划解决此题是最好不过了。 状态转移方程 F a b c d e MinFa-Si1b-Si2c-Si3d-Si4e-Si5SaleCostSi 0ltiltS 0lta b c d elt5 初始条件为 F a b c d e Cost1aCost2bCost3cCost4dCost5e 添括号问题 有一个由数字12... 9组成的数字串长度不超过200问如何将MMlt20个加号quotquot插入到这个数字串中使所形成的算术表达式的值最小。请编一个程序解决这个问题。 注意 加号不能加在数字串的最前面或最末尾也不应有两个或两个以上的加号相邻。 M保证小于数字串的长度。 例如数字串79846若需要加入两个加号则最佳方案为79846算术表达式的值133。 输入格式 从键盘读入输入文件名。数字串在输入文件的第一行行首数字串中间无空格且不折行的值在输入文件的第二行行首。 输出格式 在屏幕上输出所求得的最小和的精确值。 分析 考虑到数据的规模超过了长整型我们注意在解题过程中采用高精度算法. 规划方程: FIJ MIN FI-1K NUMK1J I-1ltKltJ-1 边界值:F0I : NUM1I FIJ表示前J个数字中添上I个加号后得到的最小值。 NUMIJ表示数字串第I位到第J位的数 上述问题的每一步都只与上一步有关。因此可以采用滚动数组 程序的时间效率约为 20 200 200 最长前缀 一些生物体的复杂结构可以用其基元的序列表示而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元字符串的序列。对于给定的基元集合P如果可以从中选出N个基元P1P2P3...Pn将它们各自对应的字符串依次连接后得到一个字符串S称S可以由基元集合P构成。在从P中挑选基元时一个基元可以使用多次也可不用。例如序列 ABABACABAAB 可以由基元集合AABBACABBC 构成。 字符串的前K个字符为该字符串的前缀其长度为K。请写一个程序对于输入的基元集合P和字符串T求出一个可以由基元集合P构成的字符串T的前缀要求该前缀的长度尽可能长输出其长度。 最长前缀 输入数据有两个输入文件 INPUT.TXTDATA.TXT INPUT.TXT 的第一行是基元集合P中的基元数目N1ltNlt100随后有2N行每两行描述一个基元第一行为该基元的长度L1ltLlt20。随后一行是一个长度为L的大写英文字符串表示该基元。每个基元互不相同。 DATA.TXT 描述要处理的字符串T.