vlambda博客
学习文章列表

【基础】一叶知秋,从背包问题到动态规划


之前我们讲解了几种典型背包问题的问题模型和解决方法。
其实,背包问题只是动态规划问题(简称DP)的冰山一角。动态规划还包含众多类型,有的问题甚至需要数据结构维护,是信息学竞赛中的一个难点,更是一个重点。
今天,我们通过对背包问题的总结,来讲解一下动态规划的基本思路。

【基础】一叶知秋,从背包问题到动态规划

首先,解决动态规划问题的基本步骤有:设置状态、枚举子问题,更新答案

我们以01背包作为例子:


【基础】一叶知秋,从背包问题到动态规划

设置状态

设置状态的关键在于找到我们的目标和哪些自变量有关系只要把这些自变量加入到状态中即可。


在这个问题中,我们要求解最大价值,考虑如何设置状态。

显然,答案(即最大价值)和每一件物品是否选择、已用背包容量有关。那么,状态的设置就要和这些要素有关。

由于答案和两个因素有关,我们很容易就能想到状态应该是一个二维的数组,一维表示当前处理的物品,一维表示已用背包容量。

枚举子问题

子问题的枚举做到不重不漏

根据设置的状态,枚举当前解决的这个小问题要从哪些更小的问题转移而来。


在01背包的问题中,我们设置了f[i][j]表示前i个物品,占用了j的空间所能达到的最大价值。

那么,我们考虑,处理第 i 个物品的时候,它的子问题显然是处理 i-1 个物品。

接着,处理占用容量为 j 时,它的子问题显然是处理容量为 j-c[i](表示选了第i个物品)和j(表示没选第i个物品)。

我们结合以上两个方面,可以找到处理 f[i][j] 的子问题是(f[i-1][j-c[i]])和(f[i-1][j])。


更新答案

在设置好状态,并找到子问题之后,就来到了DP的重头戏,更新答案,也就是设置动态转移方程。

在转移的时候,我们要思考子问题与父问题之间的关系,是取max?还是相加减?还是其他操作。


在上述例子中,由于我们要求最大价值,那么显然是用两个子问题的最大值来更新父问题。这样就能得出转移方程。

f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i])


【基础】一叶知秋,从背包问题到动态规划


接下来,我们介绍一下动态规划的适用范围。


无后效性。

无后效性是什么意思呢?

简单来说,就是父问题的决策不会对子问题的决策造成影响。

以01背包为例,无后效性是指不管第 i 个物品选或不选,都不会影响到前 i-1 个物品所做出的决策。换句话说,就是不管第i个物品选或不选,不会对f[0...(i-1)][0...V]的值产生影响。


局部最优与全局最优

另一个要求是局部最优解能推出全局最优解。

这句话应该很好理解。我们用f[i-1][j-c[i]]和f[i-1][j]的值来求解f[i][j]的值,这就是通过局部最优解来推算全局最优解。

这个概念也经常用于贪心算法之中,也是类似的意思。



在接下来的文章中,我会分不同类型再深入讲解动态规划问题,以加强大家对动态规划问题的理解。




内容下至基础编程,上至算法数据结构。

喜欢就关注吧


往期回顾


关于热点评论的传送门:





关于动态规划的传送门:

收藏 | 背包问题,一些你不知道的小技巧