动态规划算法和实例分析 动态规划算法和实例分析 n n 动态规划简介 动态规划简介 n n 0-1 0-1 背包问题 背包问题 n n 最 最 长公共子序列 长公共子序列动态规划 动态规划 简介 简介 n n 动态规划的基本 动态规划的基本 思想 思想 动态规划(DP：Dynamic Programming)是一种重要的程 序设计手段，其基本思想是在对一个问题的多阶段决策中， 按照某一顺序，根据每一步所选决策的不同，会引起状态的 转移，最后会在变化的状态中获取到一个决策序列。 动态规划就是为了使获取的决策序列在某种条件下达 到最优。动态规划是一种将多阶段决策过程转化为一系列单 阶段问题，然后逐个求解的程序设技方法。 引例：已知6种物品和一个可载重量为60的背包，物品 i(i=1,2,6)的重量w i 分别为(15,17,20,12,9,14)，产生 的效益p i 分别为(32,37,46,26,21,30)。装包时每一件物品 可以装入，也可以不装，但不可拆开装。确定如何装包，使 所得装包总效益最大。动态规划简介 动态规划简介 n n 动态规划的基本思想 动态规划的基本思想 n 引例分析
