# 本周小结!(动态规划系列三)

本周我们正式开始讲解背包问题,也是动规里非常重要的一类问题。

背包问题其实有很多细节,如果了解个大概,然后也能一气呵成把代码写出来,但稍稍变变花样可能会陷入迷茫了。

开始回顾一下本周的内容吧!

# 周一

动态规划:关于01背包问题,你该了解这些! (opens new window)中,我们开始介绍了背包问题。

首先对于背包的所有问题中,01背包是最最基础的,其他背包也是在01背包的基础上稍作变化。

所以我才花费这么大精力去讲解01背包。

关于其他几种常用的背包,大家看这张图就了然于胸了:

416.分割等和子集1

本文用动规五部曲详细讲解了01背包的二维dp数组的实现方法,大家其实可以发现最简单的是推导公式了,推导公式估计看一遍就记下来了,但难就难在确定初始化和遍历顺序上。

  1. 确定dp数组以及下标的含义

dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

  1. 确定递推公式

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. dp数组如何初始化
// 初始化 dp
vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}
1
2
3
4
5
  1. 确定遍历顺序

01背包二维dp数组在遍历顺序上,外层遍历物品 ,内层遍历背包容量 和 外层遍历背包容量 ,内层遍历物品 都是可以的!

但是先遍历物品更好理解。代码如下:

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}
1
2
3
4
5
6
7
8
  1. 举例推导dp数组

背包最大重量为4。

物品为:

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

来看一下对应的dp数组的数值,如图:

动态规划-背包问题4

最终结果就是dp[2][4]。

# 周二

动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中把01背包的一维dp数组(滚动数组)实现详细讲解了一遍。

分析一下和二维dp数组有什么区别,在初始化和遍历顺序上又有什么差异?

最后总结了一道朴实无华的背包面试题。

要求候选人先实现一个纯二维的01背包,如果写出来了,然后再问为什么两个for循环的嵌套顺序这么写?反过来写行不行?再讲一讲初始化的逻辑。

然后要求实现一个一维数组的01背包,最后再问,一维数组的01背包,两个for循环的顺序反过来写行不行?为什么?

这几个问题就可以考察出候选人的算法功底了。

01背包一维数组分析如下:

  1. 确定dp数组的定义

在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。

  1. 一维dp数组的递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
1
  1. 一维dp数组如何初始化

如果物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。

  1. 一维dp数组遍历顺序

代码如下:

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
1
2
3
4
5
6
  1. 举例推导dp数组

一维dp,分别用物品0,物品1,物品2 来遍历背包,最终得到结果如下:

动态规划-背包问题9

# 周三

动态规划:416. 分割等和子集 (opens new window)中我们开始用01背包来解决问题。

只有确定了如下四点,才能把01背包问题套到本题上来。

  • 背包的体积为sum / 2
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如何正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

接下来就是一个完整的01背包问题,大家应该可以轻松做出了。

# 周四

动态规划:1049. 最后一块石头的重量 II (opens new window)这道题目其实和动态规划:416. 分割等和子集 (opens new window)是非常像的。

本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。

动态规划:416. 分割等和子集 (opens new window)相当于是求背包是否正好装满,而本题是求背包最多能装多少。

这两道题目是对dp[target]的处理方式不同。这也考验的对dp[i]定义的理解。

# 总结

总体来说,本周信息量还是比较大的,特别对于对动态规划还不够了解的同学。

但如果坚持下来把,我在文章中列出的每一个问题,都仔细思考,消化为自己的知识,那么进步一定是飞速的。

有的同学可能看了看背包递推公式,上来就能撸它几道题目,然后背包问题就这么过去了,其实这样是很不牢固的。

就像是我们讲解01背包的时候,花了那么大力气才把每一个细节都讲清楚,这里其实是基础,后面的背包问题怎么变,基础比较牢固自然会有自己的一套思考过程。