《论文动态规划的优化讲义定稿》由会员分享，可在线阅读，更多相关《论文动态规划的优化讲义定稿（12页珍藏版）》请在金锄头文库上搜索。
1、动态规划的优化一、时间上的优化花店橱窗布置问题（IOI99试题。假 设想以最美观的方式布置花店的橱窗,有F束花，每束花的品种都不 一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位 置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目， 编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移 动，并且每束花用1到F的整数唯一标识，标识花束的整数决定了花 束在花瓶中列的顺序，即如果IVJ,则花束I必须放在花束J左边的 花瓶中。例如，假设杜鹃花的标识数为1,秋海棠的标识数为2,康 乃馨的标识数为3,所有的花束在放入花瓶时必须保持其标识数的顺 序,即：杜鹃花必须放在秋海棠左边的花瓶
2、中，秋海棠必须放在康乃 馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必 须空，即每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不 同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表 示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示:花瓶1花瓶2花瓶3花瓶4花瓶5杜鹃花723-5-2416秋海棠521-41023康乃馨-215-4-2020根据表格，杜鹃花放在花瓶2会显得非常好看，但若放在花瓶4中则显得很难看。为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆 放取得最大的美学值，如果具有
3、最大美学值的摆放方式不止一种，则 输出任何一种方案即可。题中数据满足下面条件：1WFW100, FWV W100, 50WAjW50,其中Au是花束I摆放在花瓶J中的美学值。 输入整数F, V和矩阵（A】j,输出最大美学值和每束花摆放在各个 花瓶中的花瓶编号。【分析】问题实际就是给定F束花和V个花瓶，以及各束花放到 不同花瓶中的美学值，需要你找出一种摆放的方案，使得在满足编号 小的花放进编号小的花瓶中的条件下，美学值达到最大。（1）将问题进行转化，找出问题的原型。首先，看一下上述题目 的样例数据表格。将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行 选旦只选一个数（花瓶）；摆放方案的相
4、邻两行中，下面一行的花瓶 编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给 定一个数字表格，要求编程计算从顶行至底行的一条路径，使得这条 路径所经过的数字总和最大（要求每行选旦仅选一个数字）。同时， 路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字 的列数。看到经过转化后的问题，发现问题与例题4-5的数字三角形问题 十分相似，数字三角形问题的题意是：给定一个数字三角形，要求编程计算从顶至底的一条路径，使得 路径所经过的数字总和最大（要求每行选旦仅选一个数字）。同时， 路径中相邻两行的数字，必须保证下一行数字的列数，与上一行数字 的列数相等或者等于上一行数字的列数加1。上
5、例中已经知道：数字三角形中的经过数字之和最大的最佳路径, 路径的每个中间点到最底层的路径必然也是最优的，可以用动态规划 方法求解，对于“花店橱窗布置”问题经过转化后，也可采取同样的 方法得出本题同样符合最优性原理。因此，可以对此题采用动态规划 的方法。（2）对问题原型动态规划方法的修改。“数字三角形”问题的动 态规划方法为：已知它是用行数来划分阶段。假设用ai,j表示三角 形第i行的第j个数字，用pi,j表示从最底层到ai,j这个数字的最佳 路径（路径经过的数字总和最大）的数字和，易得问题的动态转移方 程为： pn+l,j=O（lWjWn+1）pi,j=maxpi+l,j,pi+l,j+l+a
6、i,j （iWjWiWn,其中 n 为 总行数）分析两题的不同之处，就在于对路径的要求上。如果用pathi表示路 径中第i行的数字编号，那么两题对路径的要求就是：“数字三角形 要求 pathi Wpathi+lWpathi+1,而本题则要求 pathi+l JpathiJo 在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用 bi,j表示美学值表格中第i行的第j个数字，用qi,j表示从表格最底 层到bi,j这个数字的最佳路径（路径经过的数字总和最大）的数字 和，修改后的动态规划转移方程为: qi,V+l=-8 (lWiWF+1)qLFJJ=bLFJJ (iWjWV)qi,j=maxq
7、i+l,k (j VkWV+l)+bi,j (1 WiWF,l WjWV)这样，得出的maxql,j(lWjWV)就是最大的美学值，算法的时间 复杂度为0(FV2)。(3) 对算法时间效率的改进。先来看一下这样两个状态的求解方法: qi,j=maxqi+l,k(jVkWV+l)+bi,j(1 WiWF,l Wj WV)qi,j+l=maxqi+l,k (j+1 VkWV+l)+bi,j+l (lWiWF,lWj+lW V)上面两状态中求maxqi+l,k的过程进行了大量重复的比较。此时 对状态的表示稍作修改，用数组ti,j=maxqi,k(jWkWV+l) (iWi WF,1 WjWV)表示新
8、的状态。经过修改后，因为qi,j=ti+l,j+l+ai,j, 而 ti,j=maxti,j+l,qi,j (lWiWF,lWjWV),所以得出新的状态转 移方程：ti,V+l=-8(1 WiWF+1)tFJ=maxtFj+l,bFJ(iWjWV)ti,j=maxti,j+l,ti+l,j+l+ai,j(1 WiWF,l WjWV)这样，得出的最大美学值为新算法的时间复杂度为O(FxV), 而空间复杂度也为O(FxV),完全可以满足1WFWVW100的要求.分析二：，我们不妨设FL J表示在前J个花瓶中插前I朵花的最高美学值，那么我们的方程可以变为：FT, j=maxf T-l, jT+f I
9、, j, 第 I 朵花插在第 j 花 瓶里FLI, j-l第I朵花插在前j花瓶里这么以来，时间复杂度就降为了 O(N*N),这么一来，对于所有数据 都可以在瞬间出解了。股票问题。假设你有非凡的能力，能预测出今后 D天中每天的股价(设每天股价不变，第i天的为vi)。 第一天前，你有1元。以后每一天你可以用现有的资 金购买股票，或将现有的股票抛出换资金，当然也可 什么都不干。求D天后你能获得的最大收入。输入文件的第一行为D(1=DfI thenfI=fj*vt/vkendp显然，本算法的时间复杂度为O(D),空间复杂度为0(D),时间效率十分低下。如果仔细分 析，我们会发现，如果第I天的收入是山第
10、t天的抛出所得的，这就意味着从第t天后直到 第I夭一直在休息，即f(I)=f(t)成立。如果我们让f(I-l)的值能传给f(i),那么f(t)的值就能传 给f(i)。于是可以得到下面的状态转移方程二:f(i)=maxf(Il), f(j)*vi/vk (0=jkfI thenfI=fj*vi/vk endp通过进一步分析，我们可以发现，如果将前 j天所得的收入在第k天全部用来购入，这 就意味着从前第j天后直到第k天前一直在 休息，f(j)=f(k-l)成立。于是状态转移方程改 写成如下形式的状态方程三：f(i)=max(f(I-1), f(j)*vi/v(j+1) (0=jl其对应的算法描述变
11、为：Proc s3(D,vl.D);F0： =1For 1=1 to Df I: =2for j=0 to 1-1if fj*vi/vj+lfI thenfI=fj*vi/vj+lendp上述算法的时间复杂度已降为0(D%空间复杂度为0(D)。算法效率(2明显得到了提高了。 再进一步观察状态方程三，山于f(i)来源于f(I-l)和f(j)*vi/v(j+l),后者可写成vi*f(j)/v(j+l), 其中vi是固定的，f(j)/v(j+l)是待寻找的，而算法S3的最后一个循环实际上是在找最大的 f(j)/v(j+l),于是，方程三可化为：f(I)=max(f(i-l),vi*maxf(j)/v(j +1)(0=jI)=max( f(I-1), vi*g(i)其中 g(i)=max(f(j-l)/vj(Ojg then g=t7vIif g*vIf then f=g*vIendp
