最近啃动态规划,开个坑。
先从经典背包问题开始
背包问题是比较经典的动态规划问题,主要分析3类,01背包,完全背包,分组背包
01背包
01背包问题就是给定一个背包的最大容量v,以及一些物品,每个物品有自己的体积V[i]和价值W[i],要求背包内物品体积不能超过v,的情况下求总价值的最大值。01指的是每个物品只有选1个或者选0个(不选)的情况。
分析思路:动态规划问题是要确定状态表示和状态转移方程。状态表示比较难,一般可以先分类两个方向考虑–集合和集合的属性。就是我们每一个状态都表示当前问题中的一个集合,而我们的dp数组中存的就是这些集合对应的属性,一般常见的属性有max,min,len。对于这个问题,集合就是从前i个物品选,总体积小于等于j的选法,而属性,根据题意,就是所有这些选法的总价值最大值。
那么如何确定状态转移方程。可以用集合划分的思维来考虑,对于dp(i,j)来说我们可以划分为两类,选第i个物品,和不选第i个物品。那不选的话,很简单,dp[i,j]=dp[i-1,j]。那么选第i个物品的情况可以这么考虑,把第i个去掉,考虑从前i-1个物品中选体积不大于j-vi的物品价值最大,那么算上第i个物品价值最大就直接+wi。因为第i个物品价值是常数,那么我们去掉一个常数的话是不会影响最大值的结果的(后面的问题也可以这么考虑)。所以这时dp[i,j]=dp[i-1,j-vi]+wi,当然这种情况下j>=vi才可以,因为背包容积得大于第i个物品的体积,我们才能选。那么最终结果只要取这两个情况的最大值。
我们要求的就是dp(n,m)
可以写出如下代码:
1 | for(int i=1;i<=n;i++) |
dp(0,j)需要初始化成0,因为从前0个物品的选法当然是0,这里因为可以定义成全局变量就没有单独初始化了。核心模式下需要注意。
这算法还可以优化空间
注意到状态转移方程里面dp(i,j)只依赖于dp[i-1], 所以可以将状态减小为一维,把i去掉。用一维来更新状态(滚动数组)。由于我们的dp[j]是要用dp[j-v[i]],所以第二层循环应该从后往前更新,保证dp[j]是用上一轮的dp[j-v[i]]更新。
代码如下
1 | for(int i=1;i<=n;i++) |
由于变为一维了,发现当j<v[i]的时候,循环什么也不干,所以可以把判断条件删掉,直接从大于等于v[i]开始循环。
完全背包
接下来是完全背包问题,再用同样的思路分析一下。
完全背包其他条件是一样的,只是每个物品不再是只有0,1两种选择方式,可以选0-无穷多个(当然不能超过背包体积)。状态表示还是一样,现在考虑状态转移方程。从第i个物品选几个来考虑,只不过现在就有k种情况了。表示第i个物品选k个。为什么是k呢,因为肯定需要小于总体积j,不能无限选下去。
状态转移方程可以表示为如下:
dp(i,j)=max(dp(i-1,j), dp(i-1,j-vi)+wi, dp(i-1,j-2vi)+2wi, ….,dp[i-1,j-kvi]+kwi)
这里还是用上面如果不选第i个的思路来考虑,先去掉k个第i个物品,再+上k*wi。但是这个时候发现,要枚举k,那么复杂度就变成n^3。试试看有没有什么递推性质可以简化。
考虑 dp(i,j-vi)=max(dp(i-1,j-vi),dp(i-1,j-2vi)+wi, ……,dp(i-1,j-kvi)+(k-1)wi)
我们把第二个式子的第一项和我们的状态转移方程第二项对齐,可以发现!!!后面的那一部分等于dp(i,j-vi)+wi。这个其实很好理解,就是不选第i个物品。和选了第i个物品,再把他去掉,只不过这里去掉之后还是i,因为第i个物品可以选很多个,而我们并不关心选几个,直接去掉一个第i个物品,这时还是从前i个里选的,是否还有其他的第i个物品,并不知道。直接取max。
状态转移方程如下
dp(i,j)=max(dp(i-1,j),dp(i,j-vi)+wi)
这个状态转移方程,直接想很难想到,所以还是用集合划分的思路,再加上递推关系得到的。
代码如下
1 | for(int i=1;i<=n;i++) |
同理我们观察到这里也只用了i-1来更新,也可以把状态化为一维。
1 | for(int i=1;i<=n;i++) |
来看一个完全背包问题的例子
Leetcode512零钱兑换这道题还是比较直接的完全背包问题。
dp(i,j)表示用前i个面值的硬币凑出j价值的总金额的组合数,那还是分为选第i个和不选第i个的选法,那这里求的是选法的组合数所以状态转移方程为
dp(i,j)=dp(i-1,j)+dp(i,j-v[i]). 推导过程与上面相同,直接写一维的版本
代码如下
1 | class Solution { |
多重背包问题
对于多重背包问题,就是每种物品只能选有限个。状态表示还是类似的。直接看状态转移方程。
我们可以把dp(i,j),根据第i个物品选几个,分为有限种情况。
于是可以写出状态转移方程dp(i,j)=max(dp(i-1,j-v[i] x k)+w(i) x k). 其中k=0….si。 si是第i个物品可以取到的最大值。
显然根据这个状态转移方程,我们需要三重循环,下面考虑一下如何优化, 这里用到了一点位运算的思想。对于每一个k我们都可以用1+2+4…..+2^n+res来表示。所以我们可以将这si个物品打包,按照1,2,4.。。。最后还有个余数。可以这么做的原理是所有的数都可以这么来表示。于是关于第i个物品选几个的问题就可以转换为,打包后的这几堆物品选或者不选的问题。这就转化成了01背包问题
代码如下
1 |
|
这里后半部分就是优化的01背包问题代码,前半部分就是将s个物品打包为新的物品。
分组背包
这个问题稍微和前面不太一样,把物品分为N组,每组只能选一个物品
状态表示还是类似dp(i,j)表示从前i组里选,总体积不超过j的价值最大的选法。状态转移方程还是考虑第i组选第几个物品来考虑。第i组不选的话就是dp(i-1,j)。
状态转移方程可写为 dp(i,j)=max(dp(i-1,j)……dp(i-1,j-v[i,k])+w[i,k])
v[i,k])和w[i,k]表示第i组第k个物品的体积和价值。这思路转换为代码也很简单就是三重循环,枚举一下k
代码如下
1 |
|
基本的背包问题就梳理到这里。对于dp问题来说从状态表示和状态计算两个角度来考虑,这也是比较难思考的部分。可以先想朴素的表示方式,然后写出来,再看看是否能优化。