通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 动态规划精讲(二)背包动态规划

161人浏览 / 0人评论 / | 作者:whisper  | 分类: 动态规划  | 标签: leetcode  | 

作者:whisper

链接:https://www.proprogrammar.com/article/1021

声明:请尊重原作者的劳动,如需转载请注明出处


背包问题(Knapsack problem)是一种组合优化的 NP 完全问题

背包问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

  • 有 n 种物品,物品 j 的体积为 vj , 价值为 wi​ , 有一个体积限制 V。如何选择物品使得总体积不超过 V,并使得总价值最大。

这是背包问题最基础的描述,再往下细分还可以把背包问题分成几大类,其中比较基础的是 3 种:01 背包,完全背包,多重背包。


背包动态规划简介


01 背包问题

01 背包的问题描述:

有 n 种物品,物品 j 的体积为 vj,价值为 wi ,有一个体积限制 V。每种物品只有 1 个,只有选或者不选,而没有选几个的问题,此问题称为 01 背包问题。

一个朴素的想法是,只考虑价值尽量大,状态设计是单串线性 DP 中最经典的状态设计,如下:

dp[i] 表示考虑区间 [0..i] 里的物品可以取得的最大价值

由于只考虑价值,则当前物品应该尽量多拿,但是这是错的,因为后面可能有的物品虽然体积大,但是它的价值也很大,由于考虑每个物品时都尽可能多选,轮到后面的物品的时候可能就没有空间了。

因此只用价值做状态是不行的,考虑如下的状态设计:

dp[i][j] := 考虑了 [0..i]  里的物品,占用了 j 空间,所能取得的最大价值。

转移方式有两种,一种是放入,一种是不放入。如果放,则区间 [0...i-1] 只能占 j - v[i] 空间,如果不放,则区间 [0...i-1] 的物品还是占了 j 空间。

dp[i][j] = dp[i - 1][j] 当前物品不选
           dp[i - 1][j - v[i]] + w[i] 当前物品选,j - v[i] 要大于等于 0

初始化时将所有状态置为 0 即可。这就是 01 背包问题。状态设计和状态转移。一共 N \times VN×V 种状态, 状态的转移 O(1)O(1) 可以完成,因此时间复杂度,空间复杂度都是 O(NV)O(NV)。

这里还有一个衍生问题:要求背包必须放满。

这个问题可以在 01 背包的基础上改两个地方。

  1. dp 初始化是要初始化为 -1,-1 表示方案不可取。同时 dp[0][0] = 0
  2. 状态转移时,dp[i - 1][j - v[i]] + w[i] 要更新进 dp[i][j] 前,先要判断 dp[i - 1][j - v[i]] 是否为 -1,不为 -1,则 dp[i - 1][j - v[i]] 代表的物品组才能放出来

01 背包的空间优化

回顾 01 背包的基本解法的状态转移方程,如下:

dp[i][j] = dp[i - 1][j] 当前物品不选
           dp[i - 1][j - v[i]] + w[i] 当前物品选,j - v[i] 要大于等于 0

空间复杂度为 O(NV)O(NV),状态转移中 i 这一维只跟 i - 1 有关系,因此 i 这一维用滚动数组至少可以将 N 行优化为 2 行。这本来是动态规划的基本操作,在线性动态规划中很常见。这里特别提空间优化是因为 01 背包的 i 这一维用 1 行就可以解决。

假设状态只有一行,即 dp[j] := 占用了 j 空间的情况下可以取到的最大价值, 在推第 i 行的时候,dp 数组中存的是第 i - 1 行的信息。

看状态的两个转移方向,第一个是 dp[i - 1][j],这刚好就是当前 dp 数组在 j 位置保存的数据,因此不用动,比较麻烦的是另一个,就是 dp[i - 1][j - v[i]] + w[i]。这里要用到第 i - 1 行的 dp[j - v[i]],但是如果按照正常的 j 从 0 到 V 推的话,计算 dp[j] 的时候,dp[j - v[i]] 保存的已经是第 i 行信息了。

因此这里需要转换一下,从大往小推,推到 dp[j] 时,dp[j+1], dp[j+2],...,dp[V] 都已经是第 i 行的信息了,但是它们对 dp[j] 的计算没有影响,有影响的 dp[j-v[i]] 此时还是第 i - 1 行的信息,可以满足转移方程dp[i - 1][j - v[i]] + w[i] 的需要。因此当空间这一维的状态从大往小推的时候,i 这一维状态可以优化到一维。

这就是 01 背包的终极形态了。

dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推

完全背包问题

完全背包的问题描述:

有 n 种物品,物品 j 的体积为 vj ,价值为 wi ,有一个体积限制 V。每种物品有无限个,此问题称为完全背包问题。

但是由于有体积限制,因此实际取的数量也是有限制的。每个物品其实最多只能取 V / v[i] 个。

一个朴素的思路是将完全背包强行变成 01 背包:对每个物品 i,都可以求出一个 V / v[i] ,然后就 将物品展开 ,即视为有 V / v[i]个同样的物品,每个物品有选和不选两种选择。

再套用 01 背包的解法可以解决完全背包。如下:

dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推

但是这种办法复杂度太高了,需要优化。优化的方法非常巧妙,现在我们不把每个物品展开来考虑这个问题。

首先状态表示与 01 背包相同:

dp[i][j] := 考虑了区间 [0..i]  里的物品,占用了 j 空间,所能取得的最大价值。

考虑的状态转移,对于当前物品 i ,也是有两种情况:选和不选。

  • 如果选,在 01 背包中 物品区间 [0...i-1] 个只能占 j - v[i] 空间,而在完全背包中因为 i 有无限多个,因此选了 i 之后是 前 i 个物品只能占 j - v[i] 空间。
  • 如果不选,则 物品区间 [0...i-1] 还是占了 j 空间,这与 01 背包一样。状态转移方程如下,注意唯一的区别就是第 2 行的 dp[i - 1] 变成了 dp[i]。
dp[i][j] = dp[i - 1][j] 当前物品不选
           dp[i][j - v[i]] + w[i] 当前物品选,j - v[i] 要大于等于 0

 

考虑空间优化后的状态转移方程如下:在 01 背包中,由于推第 i 行的 dp[j] 时需要第 i - 1 行的 dp[j-v[i]] ,因此忌讳在推导 dp[j] 时,dp[j-v[i]] 已经更新过了, 这是 01 背包不希望发生的事,解决的办法就是 j 从大往小推。

而上述 01 背包不希望发生的事正是完全背包希望发生的,即推导第 i 行的 dp[j] 时,用到第 i 行的 dp[j -v[i]] 。而这仅需要把 01 背包中的从大往小推 j 改为从小往大推 j 即可实现。这就是完全背包的优化巧妙的地方。

dp[j] = max(dp[j], dp[j - v[i]] + w[i]) 

多重背包问题

多重背包问题是这样描述的:

有 n 种物品,物品 j 的体积为 vj ,价值为 wi ,有一个体积限制 V 。每种物品还有一个ci ,表示每种物品的个数,此问题称为多重背包问题。

思路 1 :将物品展开,全拆成 01

这与完全背包的朴素思路一致。与完全背包的情况一样,这种方法是正确的,但是时间复杂度较高。

多重背包的朴素算法与完全背包的朴素算法没有区别,而多重背包的优化相对较难,并且力扣上面没有多重背包的题目。下面仅对多重背包的优化做简单的介绍。

思路 2 :2 进制分解

这是对思路 1 的优化。

有这样一个事实:任意一个数 n,它一定可以用 1,2,4,8,... 2^k,以及 2^k到2^{k+1}之间的某个数表示。例如 13 以内的所有数都可以用 1,2,4,6 表示所以对于物品 i, 数量限制是ci
​ , 可以将其分成若干物品,它们的价值和体积为:(wi,vi),(2∗wi,2∗vi ),...

然后对这些物品做 01 背包。这样 01 背包的物品数就比思路 1 少很多了。这可以理解为类似于倍增法的思想。倍增法超出了力扣的范围,感兴趣的话可以找相关的资料学习。

以上就是背包动态规划的基本内容。背包动态规划在力扣上题目不多,下一节整理了 8 道背包动态规划的练习题,通过这些题可以大致了解背包问题的一些经典问题和常见的问法。

背包动态规划问题分析步骤


上一小节介绍了三种最基本的背包问题:01 背包,完全背包,多重背包。包括问题描述,状态设计以及状态转移方程。

实际问题会把背包问题做各种包装,而不会把问题描述的这么直白,背包的问题常见的有三种,第一个是求最值,这是背包的原始问题,第二个是体积要取到背包容量的最值,第三个是求方案数,即组合问题。

背包问题的分析步骤:

  1. 分析是否为背包问题。
  2. 是背包问题三种问法中的哪一种。
  3. 是 0-1 背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
  4. 如果是组合问题,即求方案数,是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法,不需要考虑顺序又有对应的解法,需要注意。

背包动态规划相关练习题:

  1. 最值问题
  2. 恰好取到背包容量
  3. 组合问题(求方案数)

最值问题


下面这三道题是背包问题最原始的问法,即求最大价值。

其中第三题比较特殊,没有价值,但是要求背包的剩余容量最小,以下是传统的背包做法和使得背包剩余容量最小的做法的对比。差别非常细微。

传统做法:

dp[i][j] := 考虑前 i 件物品,且背包容量为 j 时所能获得的最大价值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); 第一项是不选 i, 第二项是选 i(j - v[i] >= 0)

使得背包容量剩余最小的做法:

dp[i][j] := 考虑前 i 件物品, 背包容量为 j 时,能取到的最大体积
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i]); 第一项是不选 i, 第二项是选 i(j - v[i] >= 0)

练习题目:

  • 零钱兑换(完全背包)
  • 一和零(二维费用背包)
  • 最后一块石头的重量 II —— 转换为01背包问题,使得背包剩余容量最小

恰好取到背包容量问题


这道题是要求恰好取到背包容量的背包问题。

  • 分割等和子集(01 背包 - 要求恰好取到背包容量)

组合问题(求方案数)


这四道题是背包问题求方案数的题目,涉及到 01背包,完全背包的方案数问题。以及考虑顺序和不考虑顺序的情况。

  • 组合总和 Ⅳ —— 顺序不同的序列被视作不同的组合
  • 目标和 —— 01背包-求方案数
  • 零钱兑换 II —— 完全背包-求方案数
  • 盈利计划 —— 01背包-求方案数总价值有要求:有下限

 


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告