算法设计与分析-动态规划

算法设计与分析

DesignandAnalysisofAlgorithms1难点22023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题最优解特征分析与阶段划分计算模型地建立矩阵边乘问题最长公子序问题最大子段与问题32023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵边乘问题最长公子序问题最大子段与问题4==动态规划地设计技术==动态规划地基本设计思想将待求解问题分解成若干个子问题,分阶段求解子问题,前一阶段子问题地解成为求后续阶段子问题地解地计算信息,最后用这些子问题地最优解构造出原问题地最优解。适合用动态规划求解地问题地特征(一)子问题重叠①子问题重复②子问题地解在下一阶段决策,延续子问题多次使用s一一s一二s一三s一四s二一s二二smaxs原问题第一阶段第二阶段第三阶段最优解(二)最优子结构一个问题地最优解包含着它地子问题地最优解5例八-一有一个数塔,结点数字为其权值,按自顶向下（或自底向上）方式行走,经过地每一个结点,可以选择向左或向右走,到达底（或顶部）,求一条自顶向下（或自底向上）地路径,所经过结点权值与最大。八一一一零三一八上向底自(三)贪心八一一一四一零五八三一七九四一八七一二六一六(一)数塔八一四八九一二自顶向下(二)贪心问题分析==动态规划地设计技术==6八一一一四一零五八三一七九四一八七一二六一六(四)数塔--动态规划二一二九二一二零三九三四二九四八五零五八一层第一阶段二层第二阶段三层第三阶段四层五层第四阶段==动态规划地设计技术==第一阶段三+一八>三+七,选择结点一八,最优值二一;一七+七<一七+一二,选择结点一二,最优值二九;九+一二>九+六,选择结点一二,最优值二一;四+六<四+一六,选择结点一六,最优值二零。问题分析第二阶段一零+二一<一零+二九,选择结点一七;五+二九>五+二一,选择结点一七;八+二一>八+二零,选择结点九。第三阶段一一+三九>一一+三四,选择结点一零;一四+三四>一四+二九,选择结点五。第四阶段:八+五零>八+四八,选择结点一一。最优解所经历地结点:八一一一零一七一二7八一一一四一零五八三一七九四一八七一二六一六(四)数塔--动态规划二一二九二一二零三九三四二九四八五零五八一层第一阶段二层第二阶段三层第三阶段四层五层第四阶段==动态规划地设计技术==最优解:问题分析最优解所经历地结点:八一一一零一七一二三.二算法与数据结构==用贪心法求问题地解==计算模型(一)存储结构: data[n][n]存储原始数据信息; r[n][n]存储每一阶段地路径地计算结果; path[n][n]存储下一步最优结点列坐标。(二)计算:阶段最优r[i][j]=max{r[i+一][j],r[i+一][j+一]}+data[i][j]i=n-二,…,一;j≤i下一最优子结点地列坐标最优解data[一][一]data[二][j]data[i+一][j]……,i=j=一,j=j+path最优值 r[一][一]动态规划算法设计地基本步骤找出最优解地质,并刻画其结构特征。按最优解地质,划分子问题及演算地阶段,递推求解最优解。以自底向上或自顶向下地记忆化方法(备忘录法)计算出最优值。根据每阶段推算出地局部最优解,构造出全局最优解。92023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵边乘问题最长公子序问题最大子段与问题三.二算法与数据结构==投资分配问题==例八-二设有n万元钱,投资m个项目,将xi万元钱投入第i个项产生地效益为fi(xi),i=一,二,…,m。请问如何分配这n万元钱,使得投资地总效益最高？ 问题分析依题意,可以列出该问题地方程:目地方程 s.t. 三.二算法与数据结构==投资分配问题==第一阶段,给项目一投资,列出项目一投资地最优投资方案,其获利方程可表示为g一(x)=f一(xi),xi=零,一,二,三,四,五五万元有三种分配情况:①全部投资给某一个项目;②按比例投资给任意两个项;③按比例投资给三个项目;三.二算法与数据结构==投资分配问题==x第二阶段,加入项目二,在第一阶段地基础上求出两个项目地分配方案,获利方程可表示g二(x)=,如 g二(一)=max{f二(零)+g一(一),f二(一)+g一(零)}, g二(二)=max{f二(零)+g一(二),f二(一)+g一(一),f二(二)+g一(零)},x-三.二算法与数据结构==投资分配问题==第三阶段,加入项目三,在第二阶段地基础上求出三个项目地分配本方案,获利方程可表示g三(xi)=。xxx-x-三.二算法与数据结构计算模型(一)递推方程设k为阶段变量,零≤k≤m由问题分析可得递推方程与边界条件:(二)存储设有m个项目,投资n万元。最多m个阶段。a[][]表示某阶段最大获利情况下分配给某个项目资金。a[i][j]?f[]存储某项目初始投资所获得利润。f[i]表示投资i万元给某项目所获得地利润(数组值)。t[]存储当前投资额地最大利润g[]存储每一阶段地最优方案。运算完毕后,更新g[k]=t[k]。gain[]存储整个投资地最优分配方案。==投资分配问题==三.二算法与数据结构计算模型(三)求解最优方案a[m][n]就表示投资n万元,得到最大获利后,分配项目m地资金。设rest=n,令gain[m]=a[m][rest]表示最后一个项目在最优分配方案地最大配额。rest=rest–a[m][n]a[m-一][rest]就表示给第m-一个项目分配rest取得最大利润后,分配给第m-一个项目资金。rest=rest–a[m-一][rest]表示减去最后两个项目后地投资,则a[m-二][rest]就表示给第m-二个项目分配rest取得最大利润后,分配给第m-二个项目资金。依此类推,……就可以找到最优解==投资分配问题==三.二算法与数据结构==投资分配问题==n+一次

=(m-一)*(C二*(n+二)*(n+一)/二+(C一+C三)*(n+一))m次n+一次T(n)=O(m*n二)172023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵边乘问题最长公子序问题最大子段与问题三.二算法与数据结构例八-三背包问题(KnapsackProblem)。给定n个重量为w一,w二,…wn,价值为v一,v二,…vn地物品与一个承重为W地背包,求将这些物品地某些装入背包,在不超出重量W地情况下,价值最高地装法。问题分析依题意,可以得到如下地约束关系:目地函数s.t. ==背包问题==背包问题属于线规划问题。如果线规划问题地变量都是非负整数,则称为整数规划问题。背包问题就是整数规划问题。限制所有地xi=零或xi=一时地背包问题称为零-一背包问题。三.二算法与数据结构例八-三背包问题(KnapsackProblem)。最优子结构地证明

==背包问题==设(y一,y二,…,yn)是所给零-一背包问题地一个最优解。去掉y一,有

则(y二,…,yn)是(二)式地一个最优解。若不成立。设(z二,…,zn)是(二)式地一个最优解,则有(一)(二)>且

(y一,z二,…,zn)是所给零-一背包问题地一个更优解,从而(y一,y二,…,yn)不是所给零-一背包问题地最优解矛盾,得证三.二算法与数据结构例八-三背包问题(KnapsackProblem)。子集合及阶段划分:将每加入一个物品看成一个阶段。 将背包地承重划分为不同地重量。==背包问题==背包地限重为w(w≤W),求前i(一≤i≤n)个物品装包地最优解。设前i-一个物品装包地最优值为fi-一(w),则有两种情况:装入i物品与不装入i物品,则有fi(w)=max{fi-一(w),fi-一(w-wi)+vi}。当wi>w时,fi(w)=fi-一(w)当背包没有装入物品时,最优价值为零;非等分子问题等差递增问题拆包当背包承载为零时,不能装入物品,最优价值也为零。三.二算法与数据结构例八-三背包问题(KnapsackProblem)。计算模型(一)递推方程==背包问题==(二)存储i—表示物品编号,j表示背包当前地限载重量W—表示背包最大承载重量w[]—表示物品重量,如第i个物品地重量为w[i]v[]—表示物品价值,如第i个物品地价值为v[i]f[][]—表示在某限载情况下,背包最优装载地价值,如f[i][j]指在背包限载重量为j地情况下,第i阶段(前i个物品)最优装载地价值。三.二算法与数据结构例八-二背包问题(KnapsackProblem)。计算模型==背包问题==第一阶段,新增物品i=一,有f一(一)=f零(一)=零;//限重为一,小于w[一](w[一]=二)f一(二)=max{f零(二),f零(二-w[一])+v[一]}=max{零,f零(零)+一二}=一二;f一(三)=max{f零(三),f零(三-w[一])+v[一]}=max{零,f零(一)+一二}=一二;同理有f一(四)=一二;f一(五)=一二;第二阶段,新增物品i=二,有f二(一)=max{f一(一),f一(一-w[二])+v[二]}=max{零,f一(零)+一零}={零,一零}=一零;f二(二)=max{f一(二),f一(二-w[二])+v[二]}=max{一二,f一(一)+一零}={一二,一零}=一二;f二(三)=max{f一(三),f一(三-w[二])+v[二]}=max{一二,f一(二)+一零}={一二,二二}=二二;同理有f一(四)=二二;f一(五)=二二;第三阶段,新增物品i=三,有f三(一)=f二(一)=一零;//限重为一,小于w[三](w[三]=三)f三(二)=f二(二)=一二;//限重为二,小于w[三](w[三]=三)f三(三)=max{f二(三),f二(三-w[三])+v[三]}=max{二二,f二(零)+二零}={二二,二零}=二二;f三(四)=max{f二(四),f二(四-w[三])+v[三]}=max{二二,f二(一)+二零}={二二,三零}=三零;f三(五)=max{f二(五),f二(五-w[三])+v[三]}=max{二二,f二(二)+二零}={二二,三二}=三二;三.二算法与数据结构例八-三背包问题(KnapsackProblem)。==背包问题==五-w[四]=三三.二算法与数据结构例八-三背包问题(KnapsackProblem)。==背包问题==复杂度分析(一)问题地输入规模是n个重量w[n],n个价值v[n]及背包总承载重量W(二)第一阶段动态规划前后两部分合起来地初始化是W次除去第一阶段动态规划外,还有n-一阶段动态规划,其均包含W次优化过程,可以表示如下:

(三)回溯推导最优解所需要地计算次数为n次。总综上所述,可得T(n)=W+(n-一)(W+一)+n=n*W+二*n-一=θ(n*W)log二W,若设k=log二W,则有W=二k。当背包承载地重量很大时,它地时间复杂度实际上是T(n)=θ(n*二k)252023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵连乘问题最长公子序问题最大子段与问题三.二算法与数据结构例八-四矩阵连乘问题。设M一,M二,…Mn为n个矩阵地序列,其Mi为ri×ri+一阶矩阵,i=一,二,…,n。这个矩阵链地输入是向量R=<r零,r一,…,rn>,因为矩阵运算满足结合律,所以运算结果与计算地顺序无关,但是不同运算顺序,会造成运算时地乘法次数地不同。求以哪种乘法次序运算,使得基本运算地总次数最少。==矩阵连乘问题==问题分析多个矩阵连乘运算是满足结合律例:M一[五*二零]*M二[二零*五零]*M三[五零*一]*M四[一*一零零]可能地运算次序为:C[((M一*M二)*M三)*M四]=五*二零*五零+五*五零*一+五*一*一零零=五七五零C[M一*(M二*(M三*M四))]=五零*一*一零零+二零*五零*一零零+五*二零*一零零=一一五零零零C[(M一*(M二*M三))*M四]=二零*五零*一+五*二零*一+五*一*一零零=一六零零三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==问题分析(一)阶段划分第一阶段:一个矩阵相乘地计算量为零;第二阶段:计算两个相邻矩阵相乘地计算量,三组第三阶段:计算两个相邻矩阵相乘地结果与第三个矩阵相乘地计算量,二组第四阶段:计算三个矩阵相乘地结果与第四个矩阵相乘地计算量,一组三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==问题分析(二)阶段决策 设矩阵大小为:M一为r一×r二,M二为r二×r三,M三为r三×r四,M四为r四×r五一个矩阵"相乘"有四种情况m一一=零;m二二=零;m三三=零;m四四=零;二个矩阵相乘有三种情况:m一二=r一*r二*r三;m二三=r二*r三*r四;m三四=r三*r四*r五;三个矩阵连续相乘有二种情况:m一三=min{m一二+m三三+r一*r三*r四,m一一+m二三+r一*r二*r四}m二四=min{m二三+m四四+r二*r四*r五,m二二+m三四+r二*r三*r五}四个矩阵相乘矩阵有１种情况:m一四=min{m一一+m二四+r一*r二*r五,m一二+m三四+r一*r三*r五,m一三+m四四+r一*r四*r五}上一阶段地增益本阶段地增益三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==数学模型设求n个矩阵连乘基本运算次数为C[M一*M二*M三*……*Mn],其,Mi为ri*ri+一阶矩阵,i=一,二,三,…,n。设mi,j是计算Mi*Mi+一*…Mj地最少乘法次数(一≤i≤j≤n),对mi,j有公式:零 i=jri*ri+一*ri+二 j=i+一min(mi,k+mk+一,j+ri*rk+一*rj+一) i≤k<j,i<j因为有i≤j,所以,可设j=i+s,s=零,一,…,n-一,则有mi,j=mi,i+s。记录最优解用二维矩阵ij(n*n)来存储使mij为最小值时地k值一一=零一二=一一三=一一四=三二二=零二三=二二四=三三三=零三四=三四四=零M一[五*二零]*M二[二零*五零]*M三[五零*一]*M四[一*一零零](M一*(M二*M三))*M四三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(一)递归算法print三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(一)递归算法intcourse(inti,intj){intu,t;if(i=j)return零;if(i=j-一){[i][i+一]=i;return（r[i]*r[i+一]*r[i+二]）;}u=course(i,i)+course(i+一,j)+r[i]*r[i+一]*r[j+一];[i][j]=i;for(intk=i+一;k<j;k++){t=course(i,k)+course(k+一,j)+r[i]*r[k+一]*r[j+一];if(t<u){u=t;[i][j]=k;}}returnu;}零增益已知增益新增增益这种选择下地增益记录这种分割点偿试其它分割地方法记录每种选择下地增益根据不同地增益行最优化选择三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法分析(一)递归算法

==二O(二n-一)一-四一-一二-四一-二三-四一-三四-四二-二三-四二-三四-四一-一二-三一-二三-三一-一二-二三-三四-四定理:当n>一时,T(n)=Ω(二n-一)证:当n=二时,T(二)≥c=c一二二-一,c一=c/二.假设对于,T(k)≥c一二k-一,则T(n)≥c’(n-一)+≥c’(n-一)+=c’(n-一)+c一(二n-四)≥c一二n-一三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(二)改递归算法m[][]记录运算次数course(inti,intj){if(m[i][j]>零)returnm[i][j];if(i=j)return零;if(i=j-一){[i][i+一]=i;m[i][j]=r[i]*r[i+一]*r[i+二];returnm[i][j];}intu=course(i,i)+course(i+一,j)+r[i]*r[i+一]*r[j+一];[i][j]=i;for(intk=i+一;k<j;k++){intt=course(i,k)+course(k+一,j)+r[i]*r[k+一]*r[j+一];if(t<u){u=t;[i][j]=k;}}m[i][j]=u;returnu;}三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(二)改递归算法三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(二)非递归算法main(){intn,r[一零零],m[一零零][一零零],[一零零][一零零];input(n);for(i=一;i<=n+一;i++)input(r[i]);/初始化化数组与m。/for(i=一;i<n;i++){m[i][i]=零; \s=零\m[i][i+一]=r[i]*r[i+一]*r[i+二];\s=一\[i][i+一]=i+一;}第一阶段动态规划第二阶段动态规划三.二算法与数据结构例八-四矩阵连乘问题。==矩阵连乘问题==算法设计与描述(二)非递归算法m[n][n]=零;for(s=二;s<=n-一;s++)/动态规划过程/for(i=一;i<n-s+一;i++){j=i+s;m[i][j]=m[i][i]+m[i+一][j]+r[i]*r[i+一]*r[j+一];[i][j]=i;for(k=i+一;k<j;k++){t=m[i][k]+m[k+一][j]+r[i]*r[k+一]*r[j+一];if(t<m[i][j]){m[i][j]=t;[i][j]=k;}}}print("Theleastcalculatequantity:"m[一][n]);for(i=一;i<=n;i++){print("换行符");for(j=一;j<=n;j++)print([i][j]);}}O(n三)372023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵连乘问题最长公子序问题最大子段与问题例八-四求数列地最大子段与。给定n个元素地整数列（可能有负整数）a一,a二,···,an,求形如:

ai,ai+一,···,aji,j=一,二,···,n,i<=j

地子段与,使其为最大。当所有整数均为负整数时定义其最大字段与为零。

如(a一,a二,a三,a四,a五,a六)=(-二,一一,-四,一三,-五,-二)时最大子段与为:a二+a三+a四=二零2023/11/2138突出阶段地动态规划应用2023/11/2139开始设置初始位置best_i\best_j,最大子段与sum,当前子段与this_sum顺次选取集合元素j=零ton-一计算当前子段与this_sumthis_sum[j]=this_sum[j-一]+a[j]sum[j]=this_sum[j]bset_i=ibest_j=j比较sum[j]<this_sum[j]this_sum[j]<零新启点i=j+一输入数字序列输出最大子段结束是否是否算法一2023/11/2140算法改（算法二）2023/11/2141算法实现422023/11/21第八章动态规划主要内容投资分配问题动态规划地设计技术背包问题矩阵连乘问题最长公子序问题最大子段与问题2023/11/2143问题分析若A地长度为n,若B地长度为m,则A地子序列有:一+二+三+……+n=二n-一B地子序列有:一+二+三+……+m=二m-一如采用枚举策略,当m=n时,行串比较:一*一+二*二+三*三+……+n*n<二二n次,耗时太多,不可取。此问题不可能简单地分解成几个独立地子问题,也不能用分治法来解。所以,我们只能用动态规划地方法去解决。例八-五求两个字符序列地最长公字符子序列X="ABCBDAB"Y="BCDB"2023/11/2144算法设计一．递推关系分析设A="a零,a一,…,am-一",B="b零,b一,…,bn-一",A,B地最长公子序列为:Z="z零,z一,…,zk-一"。有以下结论:一）如果am-一=bn-一,则zk-一=am-一=bn-一,且"z零,z一,…,zk-二"是"a零,a一,…,am-二"与"b零,b一,…,bn-二"地一个最长公子序列;二）如果am-一≠bn-一,则若zk-一≠am-一,蕴涵"z零,z一,…,zk-一"是"a零,a一,…,am-二"与"b零,b一,…,bn-一"地一个最长公子序列;三）如果am-一≠bn-一,则若zk-一≠bn-一,蕴涵"z零,z一,…,zk-一"是"a零,a一,…,am-一"与"b零,b一,…,bn-二"地一个最长公子序列。2023/11/2145一）如果i=零或j=零,c[i][j]=零;二）如果i,j>零,且a[i-一]=b[j-一],c[i][j]=c[i-一][j-一]+一;三）如果i,j>零,且a[i-一]≠b[j-一],c[i][j]=max(c[i-一][j]),c[i][j-一])。

j一二三四五ibjBDCAB零ai零零零零零一A零零零零一二B零一一一一三C零一一二二四B零一一二二五D零一二二二六A零一二二三七B零一二二三六零A零零一一二二二二三三三三三四四四二．存储,子问题合并最长公子序列地长度,计算c[i][j]可递归地表述如下:2023/11/2146lcs_len(int

i,j)//计算最优值{

if(i=零orj=零)

c[i][j]=零;elseif(a[i-一]=b[j-一])c[i][j]=

lcs_len(i-一,j-一)+一

;elsec[i][j]=max(lcs_len(i,j-一),lcs_len(i-一,j));}buile_lcs(k,i,j);//构造最长公子序列{if（i=零orj=零）return;

if（c[i][j]=c[i-一][j]） buile_lcs(k,i-一,j);elseif（c[i][j]=c[i][j-一]） buile_lcs(k,i,j-一);else{str[k-一]=a[i-一];

buile_lcs(k-一,i-一,j-一);}}j一二三四五ibjBDCAB零ai零零零零零一A零零零零一二B零一一一一三C零一一二二四B零一一二二五D零一二二二六A零一二二三七B零一二二三六零A零零一一二二二二三三三三三四四四2023/11/2147算法(非递归形式)intNum=一零零

char

a[Num],b[Num],str[Num],c[Num][Num];main()

{intm,n,k;print

("Enter

two

string");

input(a,b);m=strlen(a);n=strlen(b),

k=lcs_len(n,m);buile_lcs(k,n,m);print(str);

}2023/11/2148算法(非递归)n=一零零

char

a[n],b[n],str[n];lcs_len(char

a[],

char

b[],

int

c[

][

n])

{int

m,n,i,j;

print

("Enter

two

string");

input(a,b);

m=strlen(a);n=strlen(b);for

(i=零;i<=m;i++)

c[i][零]=零;

for

(i=零;i<=n;i++)

c[零][i]=零;

for

(i=一;i<=m;i++)

for

(j=一;j<=n;j++)

if

(a[i-一]=b[j-一])

c[i][j]=c[i-一][j-一]+一;

else

if

(c[i-一][j]>=c[i][j-一])

c[i][j]=c[i-一][j];

else

c[i][j]=c[i][j-一];

retu