数据结构与算法 - 动态规划（背包问题）
转载说明
- 作者：力扣 (LeetCode)
- 链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-2-plus/
- 来源：力扣（LeetCode）
- 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
背包问题（Knapsack problem）是一种组合优化的 NP 完全问题。
背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
有 n 种物品，物品 j 的体积为 \(v_{j}\), 价值为 \(w_{i}\), 有一个体积限制 V。如何选择物品使得总体积不超过 V，并使得总价值最大。 这是背包问题最基础的描述，再往下细分还可以把背包问题分成几大类，其中比较基础的是 3 种：01 背包，完全背包，多重背包。
背包动态规划简介
背包问题
背包的问题描述
有 n 种物品，物品 j 的体积为 \(v_{j}\)，价值为 \(w_{i}\)，有一个体积限制 V。每种物品只有 1 个，只有选或者不选，而没有选几个的问题，此问题称为 ==背包问题==。
一个朴素的想法是，只考虑价值尽量大，状态设计是单串线性 DP 中最经典的状态设计，如下：
dp[i] = dp[i] 已经考虑前 i 个物品可以取得的最大价值由于只考虑价值，则当前物品应该尽量多拿，但是这是错的，因为后面可能有的物品虽然体积大，但是它的价值也很大，由于考虑每个物品时都尽可能多选，轮到后面的物品的时候可能就没有空间了。
因此只用价值做状态是不行的，考虑如下的状态设计：
dp[i][j] := 已经考虑了 [0..i-1] 前 i 个物品，占用了 j 空间，所能取得的最大价值。转移方式有两种，一种是放入，一种是不放入。如果放，则前 i - 1 个只能占 j - v[i] 空间，如果不放，则前 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 V\) 种状态, 状态的转移 O(1) 可以完成，因此时间复杂度，空间复杂度都是 O(NV)。
衍生问题：背包必须放满
回顾背包的基本解法的状态转移方程，如下：
dp[i][j] = dp[i - 1][j] 当前物品不选 dp[i - 1][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0
空间复杂度为 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 这一维状态可以优化到一维。
这就是背包的终极形态了。
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推完全背包问题
完全背包的问题描述：
有 n 种物品，物品 j 的体积为 \(v_{j}\)，价值为 \(w_{i}\)，有一个体积限制 V。每种物品有无限个，此问题称为完全背包问题。
但是由于有体积限制，因此实际取的数量也是有限制的。每个物品其实最多只能取 \(V / v[i]\) 个。
一个朴素的思路是将完全背包强行变成 01 背包：对每个物品 i，都可以求出一个 \(V / v[i]\) ，然后就 将物品展开 ，即视为有 \(V / v[i]\) 个同样的物品，每个物品有选和不选两种选择。
再套用背包的解法可以解决完全背包。如下：
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) // j 从大往小推但是这种办法复杂度太高了，需要优化。优化的方法非常巧妙，现在我们不把每个物品展开来考虑这个问题。
首先状态表示与背包相同：
dp[i][j] := 已经考虑了 [0..i-1] 前 i 个物品，占用了 j 空间，所能取得的最大价值。考虑的状态转移，对于当前物品 i ，也是有两种情况：选和不选。
如果选，在 01 背包中 前 i - 1 个只能占 j - v[i] 空间，而在完全背包中因为 i 有无限多个，因此选了 i 之后是 前 i 个物品只能占 j - v[i] 空间。
如果不选，则前 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 的体积为 \(v_{j}\) ，价值为 \(w_{i}\)，有一个体积限制 V 。每种物品还有一个 \(c_{i}\)，表示每种物品的个数，此问题称为多重背包问题。
思路 1 ：将物品展开，全拆成 01
这与完全背包的朴素思路一致。与完全背包的情况一样，这种方法是正确的，但是时间复杂度较高。
多重背包的朴素算法与完全背包的朴素算法没有区别，而多重背包的优化相对较难，并且力扣上面没有多重背包的题目。下面仅对多重背包的优化做简单的介绍。
思路 2 ：2 进制分解
这是对思路 1 的优化。
有这样一个事实：任意一个数 n，它一定可以用 1,2,4,8,...,\(2^{k}\)，以及 \(2^{k}\) 到 \(2^{k+1}\) 之间的某个数表示。例如 13 以内的所有数都可以用 1,2,4,6 表示。
所以对于物品 i, 数量限制是 \(c_{i}\), 可以将其分成若干物品，它们的价值和体积为：\((w_{i},v_{i})\)，\((2w_{i}, 2v_{i})\),...
然后对这些物品做 01 背包。这样 01 背包的物品数就比思路 1 少很多了。这可以理解为类似于倍增法的思想。倍增法超出了力扣的范围，感兴趣的话可以找相关的资料学习。
以上就是背包动态规划的基本内容。背包动态规划在力扣上题目不多，下一节整理了 8 道背包动态规划的练习题，通过这些题可以大致了解背包问题的一些经典问题和常见的问法。
背包动态规划问题分析步骤
上一小节介绍了三种最基本的背包问题：01 背包，完全背包，多重背包。包括问题描述，状态设计以及状态转移方程。
实际问题会把背包问题做各种包装，而不会把问题描述的这么直白，背包的问题常见的有三种，第一个是求最值，这是背包的原始问题，第二个是体积要取到背包容量的最值，第三个是求方案数，即组合问题。
背包问题的分析步骤：
- 分析是否为背包问题。
- 是背包问题三种问法中的哪一种。
- 是 0-1 背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
- 如果是组合问题，即求方案数，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法，需要注意。
背包动态规划相关练习题
最值问题
下面这三道题是背包问题最原始的问法，即求最大价值。
其中第三题比较特殊，没有价值，但是要求背包的剩余容量最小，以下是传统的背包做法和使得背包剩余容量最小的做法的对比。差别非常细微。
传统做法：
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 背包，完全背包的方案数问题。以及考虑顺序和不考虑顺序的情况。
- 组合总和 Ⅳ —— 顺序不同的序列被视作不同的组合
- 目标和 —— 背包问题 - 求方案数
- 零钱兑换 II —— 完全背包 - 求方案数
- 盈利计划 —— 背包问题 - 求方案数总价值有要求：有下限