动态规划及其算法应用

文超婷 沈秋铭 姚仁杰 李双喜

牡丹江师范学院计算机与信息技术学院 黑龙江牡丹江 157011

1 概述

动态规划类似于分治法。将一些待解决的问题全部分割为一个一个的小问题分别解决，一般情况下，动态规划函数是指利用子问题的重叠关系可以得到求解问题的递归关系。得到递归关系之后，就可以利用这个关系来求解问题，这也就是动态规划函数。采用动态规划算法将子问题的解通过分析表格数据存储下来，相较于分治法处理独立子问题而言，记忆化搜索可以有效地解决分治法中重复求解子问题的效率问题。

2 动态规划求解过程

动态规划的本质是对问题进行定义之后建立状态转移的方程。我们可以将动态规划的理论理解为将想要探究的问题划分成若干个小的子问题，这些子问题都有相应的解。在这些可行的解决方案中，必须有一个最优的解决方案。

如何合理地推导出求解最优值的方程，正确地找到临界值，是进行动态规划方法过程中的基本的要求。基于此，研究某个问题时先要把研究对象划分为N个密不可分的子对象，推算出其中的各个重要变量和最优值方程式，这样就把研究对象划分为N个子对象，一一推导寻求出结果。每一个临界条件，都有一个临界值，再一次求解，这样在每一个子过程求解中都可以找到最优化的结果，这样重复操作，就可以得到最后一个方程的结果，并且也可以得到研究对象的最佳计算结果。

对多个子对象的研究过程中，通常动态规划方法不同于当前对象和未来子对象，然而综合考虑当前和未来是解决最优化的关键所在，每个子对象的研究结果都要综合全局考虑，又不同于每个子对象的最优研究结果。

在求解研究对象的最佳解决方案的时候，初始条件已知，每个子对象的结果都是该子对象的状态函数，因此最优解也是通过各个子对象的各个状态一一变换时所得到的。

动态规划算法是否有效主要取决于下述的两个方面，首先，是子问题的最佳结构，其次，是子问题是否具有重叠性。

(1)最优子结构：当该问题的最佳解决方案包括了下层子问题的最优解的时候，可以说该子结构具有良好的性质。

(2)重叠子问题：当使用自顶向下的递归方法解决问题时，使用的每一个子问题都不一定是新产生的，有的时候，我们需要反复多次的计算其中的一部分子问题。在动态规划方法中，每个子问题只能求解一次，但由于子问题是重叠的，所有子问题都可以存在于表中，未来我们解决问题的同时可以尽可能多地使用这些子问题的解。

实现动态规划算法一般可以分为自顶向下递归或者自底向上递推的方法。

自顶向下是指，先划分整个数组，然后再划分子数组，直到我们所有子数组只包含一个重要元素，然后逐层合并。因此，最好使用递归来实现这一点。

自底而上是指，对整个阵列世界进行合并，可以合并相邻的两个元素，然后再对相邻的四个元素进行合并，直到将所有的数组都合并了之后，可以完成排序。

在使用动态规划来处理这个问题时，我们首先需要得到最佳解决方案的基本性质，找到其基本的结构，然后可以使用上文中的递归的方法来找到最佳的计算结果。将问题进行细化分解后，再把每一个子问题得到的最优值的有效信息通过表格形式存放，最后利用问题之间的重叠联系得到解决问题的方程组，以获得最优解的具体结果。

3 应用分析

3.1 最长公共子序列(Longest Common Subsequence)

问题描述。给两个字符串S1以及S2，求子序列在S1中且子序列也在S2中的字符串，所得的字符串的最大长度为多少。

首先定义子问题，设F(i，j)表示序列S1={x1，x2，…xn}和序列S2={y1，y2…ym}表示为最长公共子序列的长度，那么初始的子问题为序列S1和S2至少有一个空序列，因此S1和S2与空序列之间的最长公共子序列均为0，即F(i，0)=F(j，0)=F(0，0)=0。

根据图1关于字符串asdfgh以及字符串adsdg的状态矩阵，使用F[i][j]表示字符串前i个字符以及前j个字符的最长公共子序列长度。

该题目对于集合的划分有四种情况。

(1)S1[i]不在集合中，S2[j]也不在集合中。

(2)S1[i]不在集合中，S2[j]在集合中。maxlength=F[i-1][j]，由于F[i-1][j]表示在S1和S2中前i-1个字符以及前j个字符出现，但是S2[j]不一定会在F[i-1][j]的集合中出现，与条件中的S1[i]不在集合中，S2[j]在集合中不符，但是在动态规划函数中，依然可以用F[i-1][j]来表示，因为这个条件是F[i-1][j]的一个子集，而我们所需要获取的是maxlength，所以使用F[i-1][j]对maxlength的结果并不会造成影响。

(3)S1[i]在集合中，b[j]不在集合中。原理同(2)，采用F[i][j-1]表示。

(4)S2[i]在集合中，b[j]也在集合中。则maxlength=F[i-1][j-1]+1。

在实际计算中，情况(1)被包含在情况(2)(3)，因此只需要将问题划分为两种可能。

字符串asdfgh与字符串adsdg的状态矩阵表

则有如下动态规划函数：

对于该问题给出以下算法：

void LCS()

{

cin>>n>>m；

cin>>a+1>>b+1；

for(int i=1；i<=n；i++)

for(int j=1；j<=m；j++)

{

F[i][j]=max(F[i-1][j]，F[i][j-1])；//②和③的情况一定存在，所以可以无条件优先判断

if(a[i]==b[j])F[i][j]=max(F[i][j]，F[i-1][j-1]+1)；

}

cout<

}

3.2 0-1背包问题

问题描述。假设有一个背包，里面有很多东西，并且东西都有一定的价值。如果数量为n，且每件物品只能装入背包一次，在不超过背包容量的情况下，这个背包可以装入的总价值是多少？

我们将前i个物品，背包容量为j的最优解的状态设为F(i，j)，Capacity[i]为第i个物品所需的背包容量，第i个物品的价值由Value[i]来表示，目前的状态的最优解与前一个的状态的最优解有关，处于依赖关系，将F(0，0)设为初始状态，也就是第0个物品装入背包容量j=0的状态下F(0，0)=0，当我们将第0个物品装入背包容量j大于或者等于0或者前i个物品装入背包容量j为0时的情况下状态F(i，j)=0，由此可得F(0，j)=F(i，0)=0。由此可得背包容量比物品的重量小，j<第i个物品所需容量，即Capacity[i]，则第i个物品不能装入背包内，因此前i个物品能装入背包的价值最优解也就是前i-1个物品能装入背包的价值最优解，由此可得F[i][j]=F[i-1][j]。

当背包容量足以放入第i个物品，也就是j>Capacity[i]，那么我们需要做出选择，是否把第i个物品也放在里面。如果选择装入可得方程为：F[i][j]=F[i-1][j-Capacity[i]]+Value[i]；不装入的话可以得到，F[i][j]=F[i-1][j]，最后为了得到选与不选的最优解，需要对两种情况进行比较，得到的最大值max则为当前状态下的最优解。则有如下动态规划函数：

对于该问题给出以下算法：

void bag()

{

int n，m；

cin>>n>>m；

for(int i=1；i <=n；i++)

cin>>Capacity[i]>>Value[i]；

for(int i=1；i<=n；i++)

for(int j=1；j<=m；j++)

{

if(j

F[i][j]=F[i-1][j]；

else

F[i][j]=max(F[i-1][j]，F[i-1][j-Capacity[i]]+Value[i])；

}

cout<

}

根据以上分析，可以优化为一维动态规划求解。

首先，我们需要明确为什么可以简化二维的动态规划求解的思想为一维解法，因为第i项的最优值依赖并且只依赖于第i-1项的最优值，也就是说无论是i-2，i-3等的最优状态都不需要被第i项的求解使用。在背包问题上，每一个物品结束选择之后，该物品的体积和价值对于之后的最优值计算不会被利用，因此我们将二维压缩为一维即可以有效节省空间复杂度。

其次，我们需要了解当二维被简化，用一维解题时，为什么需要用逆序的方式来更新当前背包的容量的最优结果，也就是j从Capacity开始向下更新。在我们对F一维数组进行更新时，只有上一层的F数组中的数值，因此在更新下标较大的数组数值时，其上一层的F数组数值保持原始值，没被更新。所以在进行背包问题的最优问题简化到一维求解，我们需要将其的索引值从背包的总容量逐步减小进行更新。

定义状态F[j]在背包容量为j的情况下，装有N件物品的最优解，由于采用一维解法，所以利用逆向思维将背包容量j从背包的最大容量开始枚举。由此得到状态转移方程为F[j]=max(F[j]，F[j-Capacity[i]]+Value[i])。

对于该问题给出以下算法：

void bag_plus()

{

int n，m；

cin>>n>>m；

for(int i=1；i<=n；i++)

{

int Capacity，Value；

cin>>Capacity>>Value；

for(int j=m；j>=Capacity；j--)

F[j]=max(F[j]，F[j-Capacity]+Value)；

}

cout<

}

结语

采用动态规划算法以最长子序列和背包问题为切入点进行研究，探究求得最优解的方法，在最长子序列和背包问题中通过比较两种情况(b[j]不在集合中/是否装入第i个物品)分别分析两种情况的结果，得出动态规划函数，然后给出对应算法。动态规划算法无论是在日常生活还是在程序设计实训和竞赛中，都有着显著的算法地位并且被广泛使用。本研究的结果意味着当解决相关的最优解问题时，采用动态规划算法可以有效地对时间复杂度和空间复杂度进行优化和减少。后续研究中，将继续寻找优化最优解问题的其他思想。