动态规划的优化讲义.doc

动态规划的优化
一、时间上的优化
花店橱窗布置问题（IOI99试题）。假设想以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数唯一标识，标识花束的整数决定了花束在花瓶中列的顺序，即如果I＜J，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空，即每个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示：
花瓶1花瓶2花瓶3花瓶4花瓶5杜鹃花723-5-2416秋海棠521-41023康乃馨-215-4-2020根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。
为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤100，－50≤AIJ≤50，其中AIJ是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵（AIJ），输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。
【分析】问题实际就是给定F束花和V个花瓶，以及各束花放到不同花瓶中的美学值，需要你找出一种摆放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。
（1）将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。
将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数（花瓶）；摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大（要求每行选且仅选一个数字）。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的列数。
看到经过转化后的问题，发现问题与例题4-5的数字三角形问题十分相似，数字三角形问题的题意是：
给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大（要求每行选且仅选一个数字）。同时，路径中相邻两行的数字，必须保证下一行数字的列数，与上一行数字的列数相等或者等于上一行数字的列数加1。
上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径必然也是最优的，可以用动态规划方法求解，对于“花店橱窗布置”问题经过转化后，也可采取同样的方法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。
（2）对问题原型动态规划方法的修改。“数字三角形”问题的动态规划方法为：已知它是用行数来划分阶段。假设用a[i,j]表示三角形第i行的第j个数字，用p[i,j]表示从最底层到a[i,j]这个数字的最佳路径（路径经过的数字总和最大）的数字和，易得问题的动态转移方程为：p[n+1,j]=0(1≤j≤n+1)
p[i,j]=max{p[i+1,j],p[i+1,j+1]}+a[i,j](1≤j≤i≤n，其中n为总行数)
分析两题的不同之处，就在于对路径的要求上。如果用path[i]表示路径中第i行的数字编号，那么两题对路径的要求就是：“数字三角形”要求path[i]≤path[i+1]≤path[i]+1，而本题则要求path[i+1]>path[i]。
在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用b[i,j]表示美学值表格中第i行的第j个数字，用q[i,j]表示从表格最底层到b[i,j]这个数字的最佳路径（路径经过的数字总和最大）的数字和，修改后的动态规划转移方程为：
q[i,V+1]=-∞(1≤i≤F+1)
q[F,j]=b[F,j](1≤j≤V)
q[i,j]=max{q[i+1,k](j＜k≤V+1)}+b[i,j](1≤i≤F,1≤j≤V)
这样，得出的max{q[1,j]}(1≤j≤V)就是最大的美学值，算法的时间复杂度为O(FV2)。
（3）对算法时间效率的改进。先来看一下这样两个状态的求解方法：
q[i,j]=max{q[i+1,k](j＜k≤V+1)}+b[i,j](1≤i≤F,1≤j≤V)
q[i,j+1]=max{q[i+1,k](