还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《动态规划应用举例》ppt课件REPORTING目录•动态规划简介•动态规划的算法流程•动态规划应用举例-背包问题•动态规划应用举例-最长公共子序列•动态规划应用举例-斐波那契数列PART01动态规划简介REPORTING动态规划的定义01动态规划是一种通过将问题分解为相互重叠的子问题,并存储子问题的解以避免重复计算的方法02它是一种优化技术,通过将大问题分解为小问题,逐步求解,最终得到原问题的最优解动态规划的基本思想将原问题分解为子问题,并从简单子问题开始求解,逐步求解更复杂的子问题存储已解决的子问题的解,以便在需要时重复使用,避免重复计算通过自底向上的方式求解子问题,最终得到原问题的最优解动态规划的适用场景01当问题的最优解可以通过求解一系列子问题的最优解来获得时,适用动态规划02当子问题相互重叠,且子问题的解可以在后续的求解中被重复使用时,适用动态规划03当问题的规模较大,无法通过暴力法求解时,适用动态规划PART02动态规划的算法流程REPORTING阶段划分阶段划分是将问题分解为若干个阶段划分的目的是将原问题分解阶段划分的依据是问题的特征和阶段,每个阶段都有其子问题,为更小、更易于解决的小问题,性质,不同的划分方式可能导致子问题的解是构成原问题解的基以便逐个求解不同的解法础状态定义与状态转移方程状态定义是确定每个阶段的状态变量,状态变量代表01该阶段的状态状态转移方程是描述状态变量之间关系的数学表达式,02通过状态转移方程可以推导出每个阶段的解状态转移方程的建立需要分析问题的约束条件和目标03函数,以便准确描述状态变量的变化规律求解策略求解策略是动态规划算法的核存储已解决的子问题是为了避心,它包括如何选择最优子结免重复计算,提高算法的效率构、如何存储已解决的子问题、如何利用已解决的子问题来求解原问题等最优子结构是指每个子问题的利用已解决的子问题来求解原最优解是构成原问题最优解的问题是动态规划算法的核心思组成部分,因此应优先解决这想,通过将原问题转化为子问些子问题题的组合,实现问题的求解PART03动态规划应用举例-背包问题REPORTING问题描述背包问题是一个经典的动态规划问题,其目标是在给定一定重量限制的背包和一组物品中,选择一些物品放入背包,使得背包中物品的总价值最大物品的价值和重量不同,每种物品的数量是无限的问题是如何选择物品,使得在不超过背包重量限制的前提下,能够获得最大的价值状态定义与状态转移方程状态定义用dp[i][j]表示前i个物品,重量不超过j时能够获得的最大价值状态转移方程dp[i][j]=maxdp[i-1][j],dp[i-1][j-weight[i]]+value[i],其中weight[i]和value[i]分别表示第i个物品的重量和价值算法实现与结果分析算法实现首先初始化dp数组,然后根据状态转移方程逐行计算dp数组的值,直到dp[n][W](n为物品数量,W为背包的重量限制)的值被计算出来,该值即为问题的解结果分析通过动态规划的方法,我们可以将复杂的问题分解为一系列简单的子问题,并利用子问题的解来求解原问题在背包问题中,通过状态转移方程,我们可以逐步计算出dp数组的值,最终得到问题的解这种方法的时间复杂度为OnW,其中n为物品数量,W为背包的重量限制PART04动态规划应用举例-最长公共子序列REPORTING问题描述两个序列的最长公共子序列是指两个序列中最长的相同子序列例如,对于序列A为ABCDG和序列B为ABCEFG,最长公共子序列是ABCFG状态定义与状态转移方程状态定义用dp[i][j]表示序列A的前i个字符和序列B的前j个字符的最长公共子序列的长度状态转移方程dp[i][j]=maxdp[i-1][j-1],dp[i-1][j],dp[i][j-1]+1,其中dp[i-1][j-1]表示两个字符相等的情况算法实现与结果分析算法实现使用动态规划算法,按照状态转移方程逐步计算dp数组的值,最终得到最长公共子序列的长度结果分析通过算法实现,可以得出最长公共子序列的长度,并进一步分析算法的时间复杂度和空间复杂度PART05动态规划应用举例-斐波那契数列REPORTING问题描述斐波那契数列是一个经典的数列,序列的前两项是1,后续的每一项都是前两项的和我们要找出斐波那契数列中的第n项状态定义与状态转移方程定义状态Fi表示斐波那契数列的第i项状态转移方程为Fi=Fi-1+Fi-2算法实现与结果分析要点一要点二算法实现结果分析使用动态规划的方法,从第1项开始逐个计算,直到第n项动态规划方法的时间复杂度为On,空间复杂度也为On与直接计算方法相比,动态规划方法更加高效THANKS感谢观看REPORTING。