DP笔记(8)：动态规划背包相关问题学习总结——从01背包开始
Author：zhoulujun Date：
背包问题
背包问题是动态规划里的非常重要的一部分，是线性 DP 问题中一类经典而又特殊的模型。
背包问题的定义
背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 W 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？
根据物品限制条件的不同，背包问题可分为：
0-1背包问题：每种物品只能选一次，典型问题是旅行者选择物品。
完全背包问题：每种物品可以选无限次，典型问题是商品购买。
多重背包问题：每种物品有数量限制，典型问题是资源分配。
分组背包问题：物品分组，每组最多选一个，典型问题是课程教材选择。
关于这几种常见的背包，其关系如下：
几乎所有的「背包问题」都是基于「01 背包」演变而来。
当我们确定一个问题是背包问题之后，可以根据其物品的「数量限制」来判别是何种背包问题，然后套用「01 背包」的思路来求解。
背包问题的特点：
0-1 背包问题
每种物品有且仅有 1 件，可以选择不放入背包，也可以选择放入背包。
案例1
有N件物品和⼀个最多能背重量为W 的背包。第i件物品的重量是weight[i]，价值是value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥所得物品价值总和最⼤。
案例2
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
完全背包问题
每种物品可以有无限多个，可以被重复选择。
每个物品可以选择任意多个，只要总重量不超过背包容量。
典型案例：
一个商店有无限库存的几种商品，消费者在预算内选择购买哪些商品使得总价值最大化。
多重背包问题
每种物品有一定数量的限制，不能无限制选择。
每个物品可以选择0次到其数量限制次之间的任意次数。
典型案例：
在有限空间的仓库中，决定存储不同数量的多种货物以最大化总价值。
一个公司有几种资源，每种资源有一定的数量限制，如何分配这些资源以最大化收益。
分组背包问题
物品被分成若干组，每组中最多只能选择一个物品。
每个组内只能选择一个物品，所有选择的物品总重量不超过背包容量。
典型案例：
一个学生有若干个课程，每个课程有几个不同的教材可供选择，每个课程最多选一种教材，如何选择教材以使学习效果最大。
在有限的旅行空间内选择携带的装备，其中装备被分类为生存、医疗、娱乐等，每类至少需要一件。
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
每种背包问题都可以通过动态规划方法求解，但状态转移方程和问题的转换方式各有不同，需要针对具体问题进行具体分析。
背包问题基本思路
在讲解背包问题的时候，我们都是按照如下五部来逐步分析，相信大家也体会到，把这五部都搞透了，算是对动规来理解深入了。
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
其实这五部里哪一步都很关键，但确定递推公式和确定遍历顺序都具有规律性和代表性，所以下面我从这两点来对背包问题做一做总结。
明确 dp 数组的定义
第一步要明确两点，「状态」和「选择」
先说状态，如何才能描述一个问题局面？
只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是「背包的容量」和「可选择的物品」。
再说选择，也很容易想到啊，对于每件物品，你能选择什么？选择就是「装进背包」或者「不装进背包」嘛。
明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：
for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 择优(选择1，选择2...)
第二步要明确 dp 数组的定义
首先看看刚才找到的「状态」有两个，也就是说我们需要一个二维 dp 数组。
dp[i][w] 的定义如下：
对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。
状态 dp[i][w] 是一个二维数组，其中第一维代表「当前正在考虑的物品」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。
比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。
为什么要这么定义？便于状态转移，或者说这就是套路，记下来就行了。
要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。
根据这个定义，我们想求的最终答案就是 dp[N][W]。
细化上面的框架：
int[][] dp[N+1][W+1] dp[0][..] = 0 dp[..][0] = 0 for i in [1..N]: for w in [1..W]: dp[i][w] = max( 把物品 i 装进背包, 不把物品 i 装进背包 ) return dp[N][W]
确定递推公式
简单说就是，上面伪码中「把物品 i 装进背包」和「不把物品 i 装进背包」怎么用代码体现出来呢？
这就要结合对 dp 数组的定义，看看这两种选择会对状态产生什么影响：
先重申一下刚才我们的 dp 数组的定义：dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。
不放物品i：如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。
放物品i：如果你把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 val[i-1] + dp[i-1][w - wt[i-1]]。
首先，由于数组索引从 0 开始，而我们定义中的 i 是从 1 开始计数的，所以 val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量。
你如果选择将第 i 个物品装进背包，那么第 i 个物品的价值 val[i-1] 肯定就到手了，接下来你就要在剩余容量 w - wt[i-1] 的限制下，在前 i - 1 个物品中挑选，求最大价值，即 dp[i-1][w - wt[i-1]]。
综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程
可以进一步细化代码：
for i in [1..N]: for w in [1..W]: dp[i][w] = max( dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1] ) return dp[N][W]
状态转移方程 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i])，可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp数组如何初始化
背包不装物品（dp[0][w]）
无论背包载重上限是多少，前 0 件物品所能获得的最大价值一定为 0，即 dp[0][w]=0,0≤w≤W。
背包无法装物品/载重为0（ dp[i][0]）
如果背包载重上限为 0，则无论选取什么物品，可以获得的最大价值一定是 0，即 dp[i][0]=0,0≤i≤size。
对于dp[0][w]（即考虑第一个物品时），情况应该是这样的：
当w >= weight[0]时，确实可以放入第一个物品，因此dp[0][w]应该是value[0]，因为你选择拿走这个物品，这是背包能获得的唯一价值（因为只有这一个物品可选）。
但是，当w < weight[0]时，按照定义，背包无法容纳任何物品（因为第一个物品就放不进去），此时背包的最大价值应该是0，而非value[0]，因为你实际上并没有选择任何物品。
如果这样的话，就需要对数据进行初始化
for(let w = weight[0]; w <= weight.length; w++) { dp[0][w] = value[0]; }但省略初始化 dp[0][w] 也是可以的，主要是因为在动态规划的填表过程中，所有状态都会被正确地覆盖和计算，即使没有显式地初始化 dp[0][w]，在 dp[i][w] 的计算中也会自然地处理这种情况。
请看后面的最终，思考下
dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？
其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
但只不过一开始就统一把dp数组统一初始为0，更方便一些。
确定遍历顺序
先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！
很多同学做dp题目，遇到各种问题，然后凭感觉东改改西改改，怎么改都不对，或者稀里糊涂就改过了。
为什么也是可以的呢？
要理解递归的本质和递推的方向。
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]); 递归公式中可以看出dp[i][w]是靠dp[i-1][w]和dp[i - 1][w - weight[i]]推导出来的。
dp[i-1][w]和dp[i - 1][w - weight[i]] 都在dp[i][w]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
看先遍历背包，再遍历物品呢？还是同样的！
虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。
最终代码：
function zeroOnePackMethod1(weight, value, W) { // 思路 1：动态规划 + 二维基本思路
const size = weight.length;
const dp = Array.from({ length: size + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= size; i++) {// 枚举前 i 种物品
for (let w = 0; w <= W; w++) { // 枚举背包装载重量
if (w < weight[i - 1]) {// 第 i - 1 件物品装不下
dp[i][w] = dp[i - 1][w]; // dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」
} else {
// dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);
}
}
}
return dp[size][W];
}空间优化
上面使用中是用二维dp数组来讲解01背包，我们可以用滚动数组（就是把二维dp降为一维dp）来优化代码！
明确 dp 数组的定义
第一步要明确两点，「状态」和「选择」
对于背包问题其实状态都是可以压缩的。
根据之前的求解过程可以看出：当我们依次处理前 1∼n 件物品时，「前 i 件物品的处理结果」只跟「前 i−1 件物品的处理结果」，而跟之前更早的处理结果没有太大关系。
在使用二维数组的时候，递推公式：dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
在状态转移的过程中，我们只用到了当前行（第 i 行）的 dp[i][w] 以及上一行（第 i−1 行）的 dp[i−1][w]、dp[i−1][w−weight[i−1]]。
所以我们没必要保存所有阶段的状态，只需要保存上一阶段的所有状态和当前阶段的所有状态就可以了，这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了。即：dp[0][w] 保存原先 dp[i−1][w] 的状态，用dp[1][w] 保存当前 dp[i][w] 的状态。
其实我们还可以进一步进行优化，我们只需要使用一个一维数组 dp[w] 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化（去掉动态规划状态的第一维）。
在使用二维数组的时候，递推公式：dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[w]（一维数组，也可以理解是一个滚动数组）。
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。
读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
一定要时刻记住这里i和w的含义，要不然很容易看懵了。
动规五部曲分析如下：
确定dp数组的定义
在一维dp数组中，dp[w]表示：将物品装入最多能装重量为 w 的背包中，可以获得的最大价值。
一维dp数组的递推公式
dp[w]为 容量为w的背包所背的最大价值，那么如何推导dp[w]呢？
dp[w]可以通过dp[w - weight[i]]推导出来，dp[w - weight[i]]表示容量为w - weight[i]的背包所背的最大价值。
dp[w - weight[i]] + value[i] 表示 容量为 w - 物品i重量 的背包 加上 物品i的价值。（也就是容量为w的背包，放入物品i了之后的价值即：dp[w]）
此时dp[w]有两个选择，一个是取自己dp[w] 相当于 二维dp数组中的dp[i-1][w]，即不放物品i，一个是取dp[w - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，所以递归公式为：dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
可以看出相对于二维dp数组的写法，就是把dp[i][w]中i的维度去掉了。
一维dp数组如何初始化
无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 0，即 dp[w]=0,0≤w≤W。
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
dp[w]表示：容量为w的背包，所背的物品价值可以最大为dp[w]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
一维dp数组遍历顺序
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int w = bagWeight; w >= weight[i]; w--) { // 遍历背包容量
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么从大到小呢？
倒序遍历是为了保证物品i只被放入一次！但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
那么问题又来了，为什么二维dp数组遍历的时候不用倒序呢？
因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？
不可以！
因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。
（这里如果读不懂，就再回想一下dp[w]的定义，或者就把两个for循环顺序颠倒一下试试！）
所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！，这一点大家一定要注意。
最终代码
function zeroOnePackMethod2(weight, value, W) { // 思路 2：动态规划 + 滚动数组优化
const size = weight.length;
const dp = Array(W + 1).fill(0);
for (let i = 1; i <= size; i++) {// 枚举前 i 种物品
for (let w = W; w >= weight[i - 1]; w--) { // 逆序枚举背包装载重量（避免状态值错误）
// dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
dp[w] = Math.max(dp[w], dp[w - weight[i - 1]] + value[i - 1]);
}
}
return dp[W];
}0-1背包问题总结
如果是面试，要求先实现一个纯二维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写行不行？再讲一讲初始化的逻辑。
然后要求实现一个一维数组的01背包，最后再问，一维数组的01背包，两个for循环的顺序反过来写行不行？为什么？
注意以上问题都是在候选人把代码写出来的情况下才问的。
就是纯01背包的题目，都不用考01背包应用类的题目就可以看出候选人对算法的理解程度了。
三维01背包问题
给定 n 个物品，每个物品具有三个属性：体积 Vi 、重量 Wi和价值 Vi 。同时给定一个背包，具有最大容积 v和最大承重量 w。要求在不超过背包容积和承重量的前提下，求能够装入背包的最大总价值。
三维背包问题是经典的背包问题的扩展！当01背包问题有两个限制条件：载重和体积，这样01背包问题就变成了三维01背包问题。
具体来说，有 n 个物品，每个物品有三个属性：体积、重量和价值。一个背包有体积和重量的双重限制，目标是求解在不超过背包容量限制的前提下，能够获得的最大总价值。
三维背包动态五部曲解题
状态定义
使用一个三维数组 dp 来表示状态：dp[i][v][w] 表示前 i 个物品在总体积不超过 v 且总重量不超过 w 的情况下的最大总价值。
状态转移方程
对于每个物品 i，有两种选择：
不选择第 i 个物品：此时状态从 dp[i−1][v][w] 直接转移到 dp[i][v][w]。
选择第 i 个物品：此时状态从 dp[i−1][v−vi ][w−wi ] 转移到 dp[i][v][w]，并加上该物品的价值 vali。
状态转移方程为：
dp[i][v][w]=max(dp[i−1][v][w],dp[i−1][v−vi][w−wi]+vali)(如果 v≥vi 且 w≥wi)
初始状态
没有任何物品时，最大价值为0： dp[0][v][w]=0 对于所有 v 和 w。
代码实现
function threeDimensionalKnapsack(n, V, W, items) {
// 初始化 dp 数组，使用三维数组来表示状态
let dp = Array.from({ length: n + 1 }, () => Array.from({ length: V + 1 }, () =>Array(W + 1).fill(0)));
for (let i = 1; i <= n; i++) { // 填充 dp 数组
const [vi, wi, value] = items[i - 1];
for (let v = 0; v <= V; v++) {
for (let w = 0; w <= W; w++) {
dp[i][v][w] = dp[i - 1][v][w]; // 不选第 i 个物品
if (v >= vi && w >= wi) { // 选第 i 个物品
dp[i][v][w] = Math.max(dp[i][v][w], dp[i - 1][v - vi][w - wi] + value);
}
}
}
}
return dp[n][V][W];// 返回能够装入背包的最大总价值
}参考文章：
https://programmercarl.com/背包理论基础01背包-1.html
动态规划---01背包问题 https://juejin.cn/post/7149345593414909989
【动态规划/背包问题】详解「完全背包」问题 & 三种背包问题之间的内在关系
转载本站文章《DP笔记(8)：动态规划背包相关问题学习总结——从01背包开始》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9120.html