动态规划的基本要素.pptVIP

第一节动态规划的基本要素 动态规划主要用于组合优化问题，即求一个离散问题在某种意义下的最优解，有时也用于组合计数问题。 那么，什么样的问题适合用动态规划求解呢? 适合用动态规划求解的问题的两个基本要素: (1)最优子结构性质 一个问题可用动态规划有效求解的基本要求是该问题具有最优子结构性质，通俗地讲即问题的最优解包含其子问题的最优解。 实例一、数字三角形问题 1．问题描述 给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。 第二节动态规划算法步骤 (1)选择适当的问题状态表示，并分析最优解的性质； (2)递归地定义最优值(即建立递归关系)； (3)以自底向上的方式计算出最优值； (4)根据计算最优值时得到的信息，构造一个最优解。 实例二、花束摆放问题 1．问题描述 现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(F≤V)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。 2．解题思路 状态表示法一： 设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(这里k≥i)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可以通过计算max{S(F,k)?F≤k≤V}获得。 下面要分析一下这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。 容易验证，计算S[F,V]的问题具有最优子结构性质。 其递归方程为： S[i,k]=max{S[i-1,k-1]+A(i,k)，S[i,k-1]}，(i1，ki); 初始条件为： S[1,1]=A[1,1]; S[1,k]=max{A(1,k),S[1,k-1]}，(k1); S[i,i]=S[i-1,i-1]+A(i,i)， (i1) 实例三 NKOJ 1760 最大数字子串: 问题描述：输入n(1=n=1e6)和n个整数，这n个整数的绝对值均小于1000，求最大数字子串之和。 Sample Input 9 -3 4 9 2 -10 -7 11 3 -8 13 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 Sample Output 15 17 Hint 在第一组中，最大的数字子串是4 9 2的和在第二组中，最大的数字子串是2 6 -3 5 -7 14的和 -3 4 9 2 -10 -7 11 3 -8 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 显然可以在数串读入以后用有哪些信誉好的足球投注网站的方法找出这个最大子串！也很显然那样很麻烦！ 怎么办呢？考虑每输入一个数的时候便做记录，那样等数串读入完毕的时候，最大子串和到底是多少也就知道了！ 这算动态规划的一个引申! 以第一例为例： -3 4 9 2 -10 -7 11 3 -8 记录方法： -3 4 13 15 5 -7 11 14 6 把当前的最大和（含当前末尾的最大和）记录下来，虽然不能直接得出最大和是多少，但可以进行遍历有哪些信誉好的足球投注网站最大值即可！ 关键是要对负数处理好，看例二，最大子串含有负数。 -1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9 -1 2 8 ？ 如果在此处断开记录-3，那么前面的2，6 两个正数就和后边断开了，实际上2+6+（-3）0，如果后边是正数的话，完全可以加上这3个数（比如后边的5） -1 2 8 5 10 ？ 相同处理： -1 2 8 5 10 3 17 12？ 后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此处应该断开了！记录-15！ 最后-1 2 8 5 10 3 17 12 -15 1 8 4 13 ！！！ 还有一点，如果输入全为非正数的话，那么最大子串就是最大的那个数了！ 伪代码： 输入数组a[i],用数组s[i]记录