Algorithm Design and Analysis 计算机科学与技术专业课程 Algorithm Design and Analysis 算法设计与分析 宋传鸣 chmsong@lnnu.edu.cn 辽宁师范大学计算机与信息技术学院

最长公共子序列问题的描述 子序列的定义 公共子序列的定义 给定序列X={x1,x2,…,xn}和序列Z={z1,z2,…,zn},若存在一个严格递增的下标序列{i1,i2,…,ik},使得对于任意j=1,2,…,k,有zj=xij,则称Z是X的子序列 例:设X=“zxyxyz”, Z=“xyy”是X的子序列 公共子序列的定义 给定两个序列X和Y,若另一个序列Z既是X的子序列,又是Y的子序列,则称Z是X和Y的公共子序列 例:再设Y=“xyyzx”,Z=“xyy”和“xyyz”都是X和Y的公共子序列 最长公共子序列问题:给定序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的一个最长公共子序列 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的朴素解法 基本思想 时间复杂度分析 找出X序列的所有子序列,并验证其是否为Y的子序列.检查过程中记录长度最长的公共子序列 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的动态规划解法 最长公共子序列的最优子结构性质 两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列 设序列Xm={x1,x2,…,xm}和Yn={y1,y2,…,yn}的一个最长公共子序列为Z={z1,z2,…,zk},则有 如果xm=yn,那么zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列 如果xm≠yn,且zk≠xm,那么Zk是Xm-1和Yn的最长公共子序列 如果xm≠yn,且zk ≠ yn,那么Zk是Xm和Yn-1的最长公共子序列 两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的动态规划解法 建立最优解的递归结构 求最长公共子序列的递归过程 最优值的递归关系 如果xm=yn,那么只需找出Xm-1和Yn-1的最长公共子序列,然后再在其尾部加上xm 如果xm≠yn,那么分别求出Xm-1和Yn的最长公共子序列,以及Xm和Yn-1的最长公共子序列,然后从二者中取出较长者 最优值的递归关系 设c[i][j]表示序列Xi和Yj的最长公共子序列的长度,其中Xi={x1,x2,…,xi},Yj ={y1,y2,…,yj}, 则有 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的动态规划解法 计算最优值 由递归式写出递归解法,需耗费指数级时间 Xm序列仅包含m个前缀,Yn仅包含n个前缀,所以子问题的数目有 个 动态规划的求解方法:以自底向上的方式求解,以 c[i][j]存储Xi和Yj的最长公共子序列的长度,b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的动态规划解法 动态规划算法的步骤 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长公共子序列的动态规划解法 计算复杂度分析 关于空间复杂度的改进 算法中包含一个二重循环和两个二维数组 T(n)=O(mn) S(n)=O(n2) 关于空间复杂度的改进 去掉数组b 每次只保存c的两行 S(n)=O(min{n,m}) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的描述 背景举例 操作系统要处理n个请求,并且只能在0~W时间内提供服务,每个请求进程需wi时间处理.如何调度这些进程使得W时间内CPU尽可能地忙碌 形式化描述:给定n项{1,2,…,n},每项具有一个非负权值wi (i=1,2,…,n),以及一个界W,要求从n项中选出若干项组成集合S,且: 问题描述 给定n个整数(可能为负数)组成的序列a1,a2,…,an,求该序列形如 的子段和的最大值 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的朴素解法 基本思想 算法步骤 时间复杂度分析 尝试各种可能,即在任意位置开始,计算任意长度的子段和 算法包含两重循环,T(n)=O(n2) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的分治解法 基本思想 将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出两段的最大子段和 原序列的最大子段和有三种情形 等于a[1:n/2]的最大子段和 等于a[n/2+1:n]的最大子段和 等于 ,且 子问题的合并:以a[1:n/2]最后一个元素为终点的最大子段和与以[n/2+1:n]第一个元素为起始点的最大子段和的和 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的分治解法 算法步骤 计算复杂度分析 两个一重循环和两次规模为n/2的递归求解 T(n)=O(nlog2n) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的动态规划解法 最大子段和的最优子结构性质 建立最优解的递归结构 最大子段和的定义为: 令 ,则有 又 , 此时有 令 ,则有 又 , 此时有 若b[j-1]<0,则b[j]=a[j]+b[j-1]<a[j],即b[j]=a[j] 若b[j-1]>0,则b[j]>a[j],即b[j]=a[j]+b[j-1] 若b[j-1]=0,则b[j]=a[j] 建立最优解的递归结构 b[j]=max{b[j-1]+a[j],a[j]} (i≤j≤n) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

最长子段和问题的动态规划解法 算法步骤 计算复杂度分析 包含一重循环 T(n)=O(n), S(n)=O(n) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

0-1背包问题的描述 背景举例 操作系统要处理n个请求,并且只能在0~W时间内提供服务,每个请求进程需wi时间处理.如何调度这些进程使得W时间内CPU尽可能地忙碌 形式化描述:给定n项{1,2,…,n},每项具有一个非负权值wi (i=1,2,…,n),以及一个界W,要求从n项中选出若干项组成集合S,且: 矩阵连乘 最长公共子序列 最大子段和 0-1背包

0-1背包问题的描述 问题描述 给定n种物品和一个背包.物品i的重量是wi,其价值为vi,背包的容量为c.选择装入背包中的物品,使得装入背包中物品的总价值最大.注意:每种物品只有装入背包或不装入背包两种可能,故称“0-1背包” 形式化描述 给定c>0,wi>0,vi>0,1≤i≤n,要求找出n元0-1向量 (x1,x2,…,xn), xi∈{0,1},使得 ,且 达到最大,即 矩阵连乘 最长公共子序列 最大子段和 0-1背包

0-1背包问题的朴素解法 基本思想 时间复杂度分析 尝试各种可能的取法 共有2n种可能的取法 T(n)=O(2n) 矩阵连乘 最长公共子序列 最大子段和 0-1背包

0-1背包问题的动态规划解法 0-1背包问题的最优子结构性质 建立最优解的递归结构 若(y1,y2,…,yn)是0-1背包问题的一个最优解,则(y2, y3,…,yn)是下述问题的一个最优解 建立最优解的递归结构 设m(i,j)表示背包容量为j,可选择物品i,i+1,…,n时 0-1背包问题的最优值,则有 矩阵连乘 最长公共子序列 最大子段和 0-1背包 (边界条件)

0-1背包问题的动态规划解法 动态规划算法的步骤 矩阵连乘 最长公共子序列 最大子段和 0-1背包

0-1背包问题的动态规划解法 示例:假如有容量为9的背包,要装入4种重量为2,3,4和5的物品,它们的价值分别为3,4,5和7.求解该0-1背包问题 时间复杂性分析 计算量集中在二重循环, T(n)=O(cn) 矩阵连乘 最长公共子序列 最大子段和 0-1背包 j=0 1 2 3 4 5 6 7 8 9 i=1 i=2 i=3 i=4 12 4 5 7 9 11

本章回顾 动态规划算法的主要思想 动态规划算法的要素 动态规划算法与分治、备忘录算法的异同 用动态规划算法求解的几个典型问题 矩阵连乘 最长公共子序列 最大字段和 0-1背包 要求掌握用动态规划算法求解问题的原理、主要步骤,掌握典型问题的最优子结构性质的证明方法 矩阵连乘 最长公共子序列 最大子段和 0-1背包