算法设计与分析课件08动态规划

算法设计与分析Design and Analysis of Algorithms 1算法设计与分析难点点22022/9/29第第 8 章章 动态规划主要内容主要内容l投资分配问题l动态规划的设计技术l背包问题最优解特征分析与阶段划分计算模型的建立l矩阵边乘问题l最长公共子序问题l最大子段和问题算法设计与分析32022/9/29第第 8 章章 动态规划主要内容主要内容l投资分配问题l动态规划的设计技术动态规划的设计技术l背包问题l矩阵边乘问题l最长公共子序问题l最大子段和问题算法设计与分析4=动态规划的设计技术动态规划的设计技术=动态规划的基本设计思想动态规划的基本设计思想 将待求解问题分解成若干个子问题，分阶段求解子问题，前一阶段子问题的解成为求后续阶段子问题的解的计算信息，最后用这些子问题的最优解构造出原问题的最优解。适合用动态规划求解的问题的特征适合用动态规划求解的问题的特征(1)子问题重叠性子问题重复子问题的解在下一阶段决策中，延续子问题多次使用s11s12s13s14s21s22smaxs原问题第一阶段第二阶段第三阶段最优解(2)最优子结构一个问题的最优解包含着它的子问题的最优解算法设计与分析5【例8-1】有一个数塔，结点中数字为其权值，按自顶向下（或自底向上）方式行走，经过的每一个结点，可以选择向左或向右走，到达底（或顶部），求一条自顶向下（或自底向上）的路径，所经过结点权值和最大。81110318上向底自(3)贪心8111410583179418712616(1)数塔8148912自顶向下(2)贪心问题分析=动态规划的设计技术动态规划的设计技术=算法设计与分析68111410583179418712616(4)数塔-动态规划21292120393429485058一层第1阶段二层第2阶段三层第3阶段四层五层第4阶段=动态规划的设计技术动态规划的设计技术=第一阶段3+183+7，选择结点18，最优值21；17+79+6，选择结点12，最优值21；4+64+16，选择结点16，最优值20。问题分析问题分析第2阶段10+215+21，选择结点17；8+218+20，选择结点9。第3阶段11+3911+34，选择结点10；14+3414+29，选择结点5。第4阶段：8+508+48，选择结点11。最优解所经历的结点：811101712算法设计与分析78111410583179418712616(4)数塔-动态规划21292120393429485058一层第1阶段二层第2阶段三层第3阶段四层五层第4阶段=动态规划的设计技术动态规划的设计技术=最优解：问题分析问题分析最优解所经历的结点：811101712算法设计与分析3.2算法与数据结构算法与数据结构=用贪心法求问题的解用贪心法求问题的解=计算模型(1)存储结构：datann存储原始数据信息；rnn存储每一阶段的路径的计算结果；pathnn 存储下一步最优结点列坐标。最优解data11data2jdatai+1j，i=j=1，j=j+path最优值r11动态规划算法划算法设计的基本步的基本步骤(1)找出最优解的性质，并刻画其结构特征。(2)按最优解的性质，划分子问题及演算的阶段，递推求解最优解。(3)以自底向上或自顶向下的记忆化方法(备忘录法)计算出最优值。(4)根据每阶段推算出的局部最优解，构造出全局最优解。算法设计与分析92022/9/29第第 8 章章 动态规划主要内容主要内容l投资分配问题投资分配问题l动态规划的设计技术l背包问题l矩阵边乘问题l最长公共子序问题l最大子段和问题算法设计与分析3.2算法与数据结构算法与数据结构=投资分配问题投资分配问题=【例8-2】设有n万元钱，投资m个项目，将xi万元钱投入第i个项产生的效益为fi(xi)，i=1,2,m。请问如何分配这n万元钱，使得投资的总效益最高？算法设计与分析3.2算法与数据结构算法与数据结构=投资分配问题投资分配问题=第一阶段，给项目1投资，列出项目1投资的最优投资方案，其获利方程可表示为g1(x)=f1(xi)，xi=0,1,2,3,4,55万元有三种分配情况：全部投资给某一个项目；按比例投资给任意两个项；按比例投资给三个项目；算法设计与分析3.2算法与数据结构算法与数据结构=投资分配问题投资分配问题=xx-算法设计与分析3.2算法与数据结构算法与数据结构=投资分配问题投资分配问题=xxx-x-算法设计与分析3.2算法与数据结构算法与数据结构(2)存储 设有m个项目，共投资n万元。最多m个阶段。a表示某阶段最大获利情况下分配给某个项目资金。表示某阶段最大获利情况下分配给某个项目资金。aij?f存储某项目初始投资所获得利润。fi表示投资i万元给某项目所获得的利润(数组值)。t存储当前投资额的最大利润g存储每一阶段的最优方案。运算完毕后，更新gk=tk。gain存储整个投资的最优分配方案。=投资分配问题投资分配问题=算法设计与分析3.2算法与数据结构算法与数据结构计算模型(3)求解最优方案 amn就表示投资n万元，得到最大获利后，分配项目m的资金。设rest=n，令gainm=amrest表示最后一个项目在最优分配方案中的最大配额。rest=rest amn am-1rest就表示给第m-1个项目分配rest取得最大利润后，分配给第m-1个项目资金。rest=rest am-1rest表示减去最后两个项目后的投资，则am-2rest就表示给第m-2个项目分配rest取得最大利润后，分配给第m-2个项目资金。依此类推，就可以找到最优解=投资分配问题投资分配问题=算法设计与分析3.2算法与数据结构算法与数据结构=投资分配问题投资分配问题=n+1次m次n+1次T(n)=O(m*n2)算法设计与分析172022/9/29第第 8 章章 动态规划主要内容主要内容l投资分配问题l动态规划的设计技术l背包背包问题问题l矩阵边乘问题l最长公共子序问题l最大子段和问题算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。给定n个重量为w1,w2,wn，价值为v1,v2,vn的物品和一个承重为W的背包，求将这些物品中的某些装入背包中，在不超出重量W的情况下，价值最高的装法。=背包背包问题问题=背包问题属于线性规划问题线性规划问题。如果线性规划问题的变量都是非负整数，则称为整数规划问题整数规划问题。背包问题就是整数规划问题。限制所有的xi=0或xi=1时的背包问题称为0-1背包问题背包问题。算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。最优子结构的证明最优子结构的证明=背包背包问题问题=设(y1,y2,yn)是所给0-1背包问题的一个最优解。去掉y1，有则(y2,yn)是(2)式的一个最优解。若不成立。设(z2,zn)是(2)式的一个最优解，则有(1)(2)(y1,z2,zn)是所给0-1背包问题的一个更优解，从而(y1,y2,yn)不是所给0-1背包问题的最优解矛盾，矛盾，得得证算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。子集合及阶段划分：(1)将每加入一个物品看成一个阶段。(2)将背包的承重划分为不同的重量。=背包背包问题问题=背包的限重为w(wW)，求前i(1in)个物品装包的最优解。设前i-1个物品装包的最优值为fi-1(w)，则有两种情况：装入i物品和不装入i物品，则有fi(w)=max fi-1(w),fi-1(w-wi)+vi。当wiw时，fi(w)=fi-1(w)当背包没有装入物品时，最优价值为0；非等分子问题等差递增问题拆包当背包承载为0时，不能装入物品，最优价值也为0。算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。计算模型(1)递推方程=背包背包问题问题=(2)存储i表示物品编号，j表示背包当前的限载重量W表示背包最大承载重量w表示物品重量，如第i个物品的重量为wiv表示物品价值，如第i个物品的价值为vif表示在某限载情况下，背包最优装载的价值，如fij指在背包限载重量为j的情况下，第i阶段(前i个物品)最优装载的价值。算法设计与分析3.2算法与数据结构算法与数据结构【例8-2】背包问题(Knapsack Problem)。计算模型=背包背包问题问题=第1阶段，新增物品i=1，有f1(1)=f0(1)=0；/限重为1，小于w1(w1=2)f1(2)=max f0(2),f0(2-w1)+v1=max0,f0(0)+12=12;f1(3)=max f0(3),f0(3-w1)+v1=max0,f0(1)+12=12;同理有f1(4)=12;f1(5)=12;第第2阶段，新增物品段，新增物品i=2，有，有f2(1)=max f1(1),f1(1-w2)+v2=max0,f1(0)+10=0,10=10;f2(2)=max f1(2),f1(2-w2)+v2=max12,f1(1)+10=12,10=12;f2(3)=max f1(3),f1(3-w2)+v2=max12,f1(2)+10=12,22=22;同理有同理有f1(4)=22;f1(5)=22;第第3阶段，新增物品段，新增物品i=3，有，有f3(1)=f2(1)=10;/限重限重为1，小于，小于w3(w3=3)f3(2)=f2(2)=12;/限重限重为2，小于，小于w3(w3=3)f3(3)=max f2(3),f2(3-w3)+v3=max22,f2(0)+20=22,20=22;f3(4)=max f2(4),f2(4-w3)+v3=max22,f2(1)+20=22,30=30;f3(5)=max f2(5),f2(5-w3)+v3=max22,f2(2)+20=22,32=32;算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。=背包背包问题问题=5-w4=3算法设计与分析3.2算法与数据结构算法与数据结构【例8-3】背包问题(Knapsack Problem)。=背包背包问题问题=log2W，若，若设k=log2W，则有有W=2k。当背包承。当背包承载的重量很大的重量很大时，它的，它的时间复复杂度度实际上是上是T(n)=(n*2k)算法设计与分析252022/9/29第第 8 章章 动态规划主要内容主要内容l投资分配问题l动态规划的设计技术l背包问题l矩阵连乘矩阵连乘问题问题l最长公共子序问题l最大子段和问题算法设计与分析3.2算法与数据结构算法与数据结构【例8-4】矩阵连乘矩阵连乘问题问题。设M1,M2,Mn为n个矩阵的序列，其中Mi为riri+1阶矩阵，i=1,2,n。这个矩阵链的输入是向量R=，因为矩阵运算满足结合律，所以运算结果与计算的顺序无关，但是不同运算顺序，会造成运算时的乘法次数的不同。求以哪种乘法次序运算，使得基本运算的总次数最少。=矩阵连乘矩阵连乘问题问题=问题分析l多个矩阵连乘运算是满足结合律多个矩阵连乘运算是满足结合律例:M15*20*M220*50*M350*1*M41*100可能的运算次序为：C(M1*M2)*M3)*M4=5*20*50+5*50*1+5*1*100=5750 CM1*(M2*(M3*M4)=50*1*100+20*50*100+5*20*100=115000 C(M1*(M2*M3)*M4=20*50*1+5*20*1+5*1*100=1600 算法设计与分析3.2算法与数据结构算法与数据结构【例8-4】矩阵连乘矩阵连乘问题问题。=矩阵连乘矩阵连乘问题问题=问题分析(1)阶段划分 第1阶段：一个矩阵相乘的计算量为0;第2阶段：计算两个相邻矩阵相乘的计算量,共3组第3阶段：计算两个相邻矩阵相乘的结果与第三个矩阵相乘的计算量,共2组第4阶段：计算三个矩阵相乘的结果与第四个矩阵相乘的计算量,共1组算法设计与