最优解问题中动态规划的应用以及算法优化

周益民+陈艳碧

摘要：本文介绍了动态规划的算法思想和实现步骤。以各类背包问题为例，阐述动态规划的算法思想在最优解问题中的优势，以及和其他算法之间的对比，并对传统的动态规划算法进行时间复杂度和空间复杂度上的优化。

1 动态规划的基本原理

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

2 动态规划的适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

a.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

b.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

c.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

3 动态规划应用实例---背包问题

3.1 01背包问题

3.1.1 题目

有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是 Ci1得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

3.1.2 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i，v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

F[i，v]=max{F[i-1，v]，F[i-1，v-Ci]+Wi}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为 v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i-1件物品相关的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为F[i-1，v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”，此时能获得的最大价值就是F[i-1，v-Ci]再加上通过放入第i件物品获得的价值Wi。

3.1.3 优化空间复杂度

以上方法的时间和空间复杂度均为O（V N），其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O（V）。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i←1...N，每次算出来二维数组F[i，0...V]的所有值。那么，如果只用一个数组F[0...V]，能不能保证第i次循环结束后F[v]中表示的就是我们定义的状态F[i，v]呢？F[i，v]是由F[i-1，v]和F[i-1，v-Ci]两个子问题递推而来，能否保证在推F[i，v] 时（也即在第i次主循环中推F[v]时）能够取用F[i-1，v]和F[i-1，v-Ci] 的值呢？事实上，这要求在每次主循环中我们以v←V...0的递减顺序计算F[v]，这样才能保证计算F[v]时F[v-Ci]保存的是状态F[i-1，v-Ci] 的值。

3.1.4 初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包。那么在初始化时除了F[0]为0，其它F[1..V]均设为-∞，这样就可以保证最终得到的F[V] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F[0..V]全部设为0。这是为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为0，所以初始時状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解。

3.1.5 一个常数优化

上面伪代码中的 for i ← 1 to N for v ← V to Ci

中第二重循环的下限可以改进。它可以被优化为

for i← 1 to N

for v ← V to max（V -ΣN iWi，Ci）

3.1.6 小结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思 想。另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。

4 结语

动态规划的算法思想在解决类似背包问题的最优解问题中有很好的应用，我认为动态规划的思想有别于其他分治方法的地方在于它是用于解决不连续、矢量化数据的首选。因为数据的不连续导致其他算法例如：分治算法、贪心算法都不能得到该种问题下的最优解。

参考文献：

[1]傅清祥，王晓东，算法与数据结构，电子工业出版社，1998

[2]现代应用数学手册——运筹学与最优化理论卷，清华大学出版社，1998

[3]来煜坤，把握本质，灵活运用——动态规划的深入探讨，中国NOI国家集训队论文集

[4]李刚，动态规划的深入讨论，中国NOI国家集训队论文集

作者简介：

周益民（1996.01.22-）男，汉族，身份证号：500224199601220035，本科生，重庆铜梁，研究方向：地理信息科学

陈艳碧（1996.02.16-）女，汉族，身份证号：530323199602160104，本科生，云南曲靖，研究方向：地理信息科学endprint