软件设计师考试|软件设计师考试 | 第八章 算法设计与分析 | 动态规划法

(一)动态规划法的基本思想 动态规划算法与分治法类似,其基本思想也是将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题,则相同的子问题会被求解多次,以至于最后解决原问题需要耗费指数级时间。然而,不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案,在需要时再找出已求得的答案,这样就可以避免大量的重复计算,从而得到多项式时间的算法。为了达到这个目的,可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解,每个解都对应于一个值,我们希望找到具有最优值的那个解。
【软件设计师考试|软件设计师考试 | 第八章 算法设计与分析 | 动态规划法】设计一个动态规划算法,通常按照以下步骤来进行:

  1. 找出最优解的性质,并刻画其结构特征。
  2. 递归地定义最优解的值。
  3. 以自底向上的方式计算出最优值。
  4. 根据计算最优值时得到的信息,构造一个最优解。
使用动态规划法时需要满足的两个性质:
  • 最优子结构
    如果一个问题的最优解中包含了其子问题的最优解,就说明该问题具有最优子结构。
    当一个问题具有最优子结构时,提示我们动态规划法可能会适用,但是此时贪心策略可能也是适用的。
  • 重叠子问题
    重叠子问题指用来解原问题的递归算法可反复地解同样的子问题,而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时,就说该问题包含重叠子问题。此时若用分治法递归求解,则每次遇到子问题都会视为新问题,会极大地降低算法的效率,而动态规划法总是充分利用重叠子问题,对每个子问题仅计算一次,把解保存在一个在需要时就可以查看的表中,而每次查表的时间为常数。
(二)动态规划法的典型实例 动态规划法的典型实例包括:背包问题,最长公共子序列。
其中,背包问题是假设有n个物品,第i个物品价值为vi,重量为wi,,其中viwi均为非负数,背包的容量为WW为非负数。现在要考虑如何选择装入背包的物品,使得装入背包的物品的总价值最大。
解决背包问题的思路是:
  1. 刻画背包问题的最优解的结构。
    将背包问题的求解过程看作是进行一系列的决策过程。
    如果一个问题的最优解包含了物品n,即Xn = 1,那么其余的X1、X2、……、Xn-1一定构成子问题1、2、……、n-1在容量W-Wn时的最优解。
    如果这个最优解不包含物品n,即Xn = 0,那么其余的X1、X2、……、Xn-1一定构成子问题1、2、……、n-1在容量为W时的最优解。
  2. 递归定义最优解的值。
    根据步骤一分析的最优解的结构递归地定义问题最优解。
  3. 计算背包问题最优解的值。
    基于上述递归式,以自底向上的方式计算最优解的值。
  4. 根据计算的结果构造问题最优解。

    推荐阅读