@[toc]
一、背包问题简介
参考：
- 【资料】算法通关手册、背包九讲 - 崔添翼
- 【文章】背包 DP - OI Wiki
- 【B站视频】代码随想录详解0-1背包
背包问题：背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 $W$ 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？
根据物品限制条件的不同，背包问题可分为：
- 0-1 背包问题
- 完全背包问题
- 多重背包问题
- 分组背包问题
- 混合背包问题
背包问题的暴力解题思路
背包问题的暴力解题思路比较简单。假设有 $n$ 件物品。我们先枚举出这 $n$ 件物品所有可能的组合（每个物品都是取与不取两个状态）。然后再判断这些组合中的物品是否能放入背包，以及是否能得到最大价值。这种做法的时间复杂度是 $O(2^n)$。
背包问题暴力解法的时间复杂度是指数级别的，我们可以利用动态规划算法减少一下时间复杂度。下面我们来讲解一下如何使用动态规划方法解决各种类型的背包问题。
二、 0-1 背包问题
- 0-1 背包问题：有 $n$ 件物品和有一个最多能装重量为 $W$ 的背包。第 $i$ 件物品的重量为 $weight[i]$，价值为 $value[i]$，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
- 0-1 背包问题的特点：每种物品有且仅有 $1$ 件，可以选择不放入背包，也可以选择放入背包。
2.1 二维dp解法
假如有编号0到2三件物品，其重量和价值分别为：
物品|重量 |价值
———— | ——-|——
物品0| 1| 15
物品1| 3| 20
物品2| 4| 30
现在背包重量为4，求其能装的物品最大价值是多少？
本题根据二维dp数组构造时，第一行是否表示0个物品</font >，有两种写法，其初始化也略有不同。
2.1.1 第一行表示第一个物品
- 划分阶段
按照物品的序号、当前背包的载重上限进行阶段划分。- 定义状态
构造二维数组，每行表示遍历的物品编码，每列表示遍历的背包重量dp[i][j]表示遍历到第i个物品，背包剩余容量为j时，背包所装物品的最大价值。
- 状态转移方程
前i个物品的最大价值dp[i][j]，可以由前i-1个物品的最大价值转换而来，这取决于是否放入第i个物品：
- 不放物品
i：此时dp[i][j]=dp[i - 1][j]；
当物品i的重量大于背包剩余容量j时，物品i无法放进背包中，背包内的价值依然和前面相同。 - 放物品
i：dp[i-1][j-weight[i]]为背包容量j-weight[i]时候不放物品i的最大价值，放入物品i后，其价值为dp[i - 1][j - weight[i]] + value[i] - 最终结果取上述两种情况的最大值，即$max \lbrace dp[i - 1][w], \quad dp[i - 1][w - weight[i ]] + value[i] \rbrace$
最终 dp[i][j] 取上述两种方式的最大值，所以状态转移方程为：
个人理解，之所以背包问题可以求得限定重量下的最大值，就在于每个阶段都取到当前的最优解，而这个最优解是每次都考虑是否取物品
i而得来的，即$dp[i][j]=max \lbrace dp[i - 1][w], \quad dp[i - 1][w - weight[i ]] + value[i] \rbrace$
- 状态初始化
- 重量为0时，值为0，即
dp[i][0]=0- 根据重量w是否大于value[0]，判断第一行是否可以装入物品0。
- 最终结果
根据我们之前定义的状态，最终结果为 $dp[size][W]$，其中 $n$ 为物品的件数，$W$ 为背包的载重上限。
class Solution: |
2.1.2 第一行表示0个物品
上述解法中，要根据重量W是否大于value[0]来判断第一行取值，单独进行初始化。为了简化这一步，可以将第一行表示为0个物品，这样第一行也初始化为0。
另外因为第一列也要初始化为0（dp[i][0]=0），所以整个dp数组都初始化为0 就行，简化了初始化步骤。唯一不同的是，构造dp数组时，dp=[[-1]*(W+1) for _ in range(n+1)] ，遍历物品数是物品数量+1
划分阶段
按照物品的序号、当前背包的载重上限进行阶段划分。定义状态
- 定义状态 $dp[i][w]$ 表示为：前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。
- 状态 $dp[i][w]$ 是一个二维数组，其中第一维代表「当前正在考虑的物品」</font >，第二维表示 「当前背包的载重上限」</font >，二维数组值表示「可以获得的最大价值」。
状态转移方程
根据第
i-1件物品放与不放，可将问题转换为一个只跟前 $i - 1$ 件物品相关的问题。- 第 $i - 1$ 件物品不放入背包：问题转换为「前 $i - 1$ 件物品放入一个最多能装重量为 $w$ 的背包中 ，可以获得的最大价值」，即 $dp[i - 1][w]$。
- 第 $i - 1$ 件物品放入背包：问题转换为「前 $i - 1$ 件物品放入一个最多能装重量为 $w - weight[i - 1]$ 的背包中，可以获得的最大价值」为 $dp[i - 1][w - weight[i - 1]]$，再加上「放入的第 $i - 1$ 件物品的价值」为 $value[i - 1]$，则此时可以获得的最大价值为 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$。
接下来我们再来考虑一下第 $i - 1$ 件物品满足什么条件时才能考虑是否放入背包，并且在什么条件下一定不能放入背包。
- 如果当前背包的载重不足时（即 $w < weight[i - 1]$）：第 $i - 1$ 件物品一定不能放入背包，此时背包的价值 $dp[i][w]$ 仍为 $dp[i - 1][w]$ 时的价值，即 $dp[i][w] = dp[i - 1][w]$。
- 如果当前背包的载重足够时（即 $w \ge weight[i - 1]$）：第 $i - 1$ 件物品可以考虑放入背包，或者不放入背包，此时背包的价值取两种情况下的最大值，即 $dp[i][w] = max \lbrace dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1] \rbrace$。
- 则状态转移方程为：
初始条件
- 如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[i][0] = 0$。
- 前 $0$ 件物品所能获得的最大价值一定为 $0$，即 $dp[0][w] = 0$。
最终结果
根据我们之前定义的状态，$dp[i][w]$ 表示为：前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[size][W]$，其中 $size$ 为物品的件数，$W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W)$，其中 $n$ 为物品数量，$W$ 为背包的载重上限。
- 空间复杂度：$O(n \times W)$。
2.2 一维dp解法
2.2.1 使用两个一维数组
二维dp的状态转移方程为：
由此可知，第 $i$ 行的值 $dp[i][w]$ ，只跟上一行的状态$dp[i - 1][w]$、$dp[i - 1][w - weight[i - 1]]$有关。这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了。即：用 $dp[0][w]$ 保存原先 $dp[i - 1][w]$ 的状态，用 $dp[1][w]$ 保存当前 $dp[i][w]$ 的状态。class Solution:
# 思路 2：动态规划 + 滚动数组优化
def zeroOnePackMethod2(self, weight: [int], value: [int], W: int):
size = len(weight)
dp = [0] * (W+1)
# 枚举前 i 种物品
for i in range(1, size + 1):
dp2 = [0] * (W+1)
for j in range(W+1):
if j < nums[i-1]: # 容量有限，无法选择第i个数字nums[i-1]
dp2[j] = dp[j]
else: # 可选择第i个数字nums[i-1]，也可不选【两种方式之和】
dp2[j] = max(dp[j] , dp[j-weight[i-1]]+value[i-1]
dp = dp2
return dp[W]
- 时间复杂度：$O(n \times W)$，其中 $n$ 为物品数量，$W$ 为背包的载重上限。
- 空间复杂度：$O(W)$。
2.2.2 使用一个一维数组
更进一步的，我们将上一行的状态复制到当前行，然后在当前行进行计算，这样只需要使用一个一维数组 $dp[w]$ 就可以了。
每次都将上一层覆盖到当前层进行计算，再覆盖到下一层计算……，每次计算都在更新数组，这就是「滚动数组」的由来，最终去掉动态规划状态的第一维。
划分阶段
按照当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。状态转移方程
- 不放物品
i-1时，将上一层数组复制下来，所以也是$dp[w]$ - 放入物品
i-1时，则为$dp[w - weight[i - 1]] + value[i - 1]$
- 不放物品
最终取最大就是dp[w]的值：
$dp[w] = \begin{cases} dp[w] & w < weight[i - 1] \cr max \lbrace dp[w], dp[w - weight[i - 1]] + value[i - 1] \rbrace & w \ge weight[i - 1] \end{cases}$
- 倒序遍历（保证每个物品只被选取一次）
在第 $i$ 轮计算之前，$dp[w]$ 中保存的是「第 $i - 1$ 阶段的所有状态值」。在第 $i$ 轮计算之后，$d[w]$ 中保存的是「第 $i$ 阶段的所有状态值」。
为了保证第 $i$ 轮计算过程中，$dp[w]$ 是由第 $i - 1$ 轮中 $dp[w]$ 和 $dp[w - weight[i - 1]]$ 两个状态递推而来的值，我们需要按照「从 $W \sim 0$ 逆序的方式」倒推 $dp[w]$。
这是因为如果我们采用「从 $0 \sim W$ 正序递推的方式」递推 $dp[w]$，如果当前状态 $dp[w - weight[i]]$ 已经更新为当前第 $i$ 阶段的状态值。那么在向右遍历到 $dp[w]$ 时，我们需要的是第 $i - 1$ 阶段的状态值（即上一阶段的 $dp[w - weight[i - 1]]$），而此时 $dp[w - weight[i - 1]]$ 已经更新了，会破坏当前阶段的状态值，从而无法推出正确结果。
而如果按照「从 $W \sim 0$ 逆序的方式」倒推 $dp[w]$ 则不会出现该问题。
因为 $w < weight[i - 1]$ 时，$dp[w]$ 只能取上一阶段的 $dp[w]$，其值相当于没有变化，这部分可以不做处理。所以我们在逆序倒推 $dp[w]$ 时，只需遍历到 $weight[i - 1]$ 时即可。
初始条件
- $dp[0] = 0$。
- dp数组中其它数值也必须初始化为0，因为涉及到计算$max(dp[w],dp[w - weight[i - 1]] + value[i - 1]$
最终结果
根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W)$，其中 $n$ 为物品数量，$W$ 为背包的载重上限。
- 空间复杂度：$O(W)$。
2.3 0-1背包应用
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0416 | 分割等和子集 | Python | 数组、动态规划 | 中等 |
| 0494 | 目标和 | Python | 深度优先搜索、动态规划 | 中等 |
| 1049 | 最后一块石头的重量 II | Python | 数组、动态规划 | 中等 |
2.3.1 分割等和子集（最大背包价值）
给定一个只包含正整数的非空数组 $nums$，判断是否可以将这个数组分成两个子集，使得两个子集的元素和相等。
- $1 \le nums.length \le 200$。
- $1 \le nums[i] \le 100$。
示例：
输入：nums = [1,5,11,5] |
思路 1：动态规划
这道题换一种说法就是：从数组中选择一些元素组成一个子集，使子集的元素和恰好等于整个数组元素和的一半。这样的话，这道题就可以转变为「0-1 背包问题」。
- 把整个数组中的元素和记为 $sum$，把元素和的一半 $target = \frac{sum}{2}$ 看做是「0-1 背包问题」中的背包容量。
- 把数组中的元素 $nums[i]$ 看做是「0-1 背包问题」中的物品。
- 第 $i$ 件物品的重量为 $nums[i]$，价值也为 $nums[i]$。
- 因为物品的重量和价值相等，如果能装满载重上限为 $target$ 的背包，那么得到的最大价值也应该是 $target$。
这样问题就转变为：给定一个数组 $nums$ 代表物品，数组元素和的一半 $target = \frac{sum}{2}$ 代表背包的载重上限。其中第 $i$ 件物品的重量为 $nums[i]$，价值为 $nums[i]$，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限的情况下，能否将背包装满从而得到最大价值？
划分阶段
按照当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[w]$ 表示为：从数组 $nums$ 中选择一些元素，放入最多能装元素和为 $w$ 的背包中，得到的元素和最大为多少。状态转移方程
$dp[w] = \begin{cases} dp[w] & w < nums[i - 1] \cr max \lbrace dp[w], \quad dp[w - nums[i - 1]] + nums[i - 1] \rbrace & w \ge nums[i - 1] \end{cases}$初始条件
如果背包容量为 $0$，则无论选取什么元素，可以获得的元素和一定是 $0$，即 $dp[0] = 0$。最终结果
根据我们之前定义的状态，$dp[target]$ 表示为：从数组 $nums$ 中选择一些元素，放入最多能装元素和为 $target = \frac{sum}{2}$ 的背包中，得到的元素和最大值。
所以最后判断一下 $dp[target]$ 是否等于 $target$。如果 $dp[target] == target$，则说明集合中的子集刚好能够凑成总和 $target$，此时返回True；否则返回False。
2.3.1.1 二维dp数组
for i in range(n)class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
s=sum(nums)
if s%2==1:
return False
weight=s/2
n=len(nums)
# dp矩阵的行代表物品，列代表重量，第一行表示第一种物品
dp=[[-1]*(weight+1) for _ in range(n)]
# 重量为0时值为0，即初始化dp[i][0] = 0
for i in range(n):
dp[i][0]=0
# 第1行，重量≥nums[0]时才初始化为nums[0]
for j in range(weight+1):
if j>=nums[0]:
dp[0][j]=nums[0]
# 遍历物品
for i in range(n):
for j in range(weight+1):
if j<nums[i]:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
return dp[n-1][weight]==weightfor i in range(1,n+1)class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
s=sum(nums)
if s%2==1:
return False
weight=s/2
n=len(nums)
# dp矩阵的行代表物品，列代表重量，第一行表示第一种物品
dp=[[0]*(weight+1) for _ in range(n+1)]
# 遍历物品
for i in range(1,n+1):
for j in range(weight+1):
if j<nums[i-1]:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1])
#print(dp)
return dp[n-1][weight]==weight
2.3.1.2 一维dp数组
class Solution(object): |
等同于：
for i in range(n): # 遍历物品 |
也可以是：
for i in range(1,n+1): # 遍历物品 |
- 时间复杂度：$O(n \times target)$，其中 $n$ 为数组 $nums$ 的元素个数，$target$ 是整个数组元素和的一半。
- 空间复杂度：$O(target)$。
2.3.2 目标和（装满背包的方式）
给定一个整数数组 nums 和一个整数 target。数组长度不超过 20。向数组中每个整数前加 + 或 -。然后串联起来构造成一个表达式。
返回通过上述方法构造的、运算结果等于 target 的不同表达式数目。
示例：输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
2.3.2.1 记忆化搜索
使用哈希表 $table$ 记录遍历过的位置 $i$ 及所得到的的当前和cur_sum 下的方案数，来避免重复搜索。具体步骤如下：
- 定义从位置 $0$、和为 $0$ 开始，到达数组尾部位置为止，和为 $target$ 的方案数为
dfs(0, 0)。 - 下面从位置 $0$、和为 $0$ 开始，以深度优先搜索遍历每个位置。
- 如果当前位置 $i$ 遍历完所有位置：
- 如果和
cur_sum等于目标和 $target$，则返回方案数 $1$。 - 如果和
cur_sum不等于目标和 $target$，则返回方案数 $0$。
- 如果和
- 如果当前位置 $i$、和为
cur_sum之前记录过（即使用 $table$ 记录过对应方案数），则返回该方案数。 - 如果当前位置 $i$、和为
cur_sum之前没有记录过，则：- 递归搜索 $i + 1$ 位置，和为
cur_sum - nums[i]的方案数。 - 递归搜索 $i + 1$ 位置，和为
cur_sum + nums[i]的方案数。 - 将上述两个方案数加起来就是当前位置 $i$、和为
cur_sum的方案数，将其记录到哈希表 $table$ 中，并返回该方案数。
- 递归搜索 $i + 1$ 位置，和为
- 最终方案数为
dfs(0, 0)，将其作为答案返回
class Solution: |
- 时间复杂度：$O(2^n)$。其中 $n$ 为数组 $nums$ 的长度。
- 空间复杂度：$O(n)$。递归调用的栈空间深度不超过 $n$。
2.3.2.2 二维dp数组
1. 解题思路
假设数组中所有元素和为 sum，数组中所有符号为 + 的元素为 pos，符号为 - 的元素和为neg。则 target = pos-neg。而 sum=pos+neg。根据两个式子可以求出 neg=(sum-target)/2。
那么这道题就变成了，如何在数组中找到一个集合，使集合中元素和为 (target + sum) / 2。这就变为了求容量为 (target + sum) / 2 的 0-1 背包问题。
对于本题而言，nums[i] 则对应于常规背包问题中第 i 件物品的重量。我们要做的是从数组 nums 中选出若干个数字（每个元素最多选一次）使得其和刚好等于 (target + sum) / 2 ，并计算有多少种不同的选择方式。
2. 解题步骤
- 定义：定义
dp[i][j]表示：从前 i 个数字中选出若干个，使得被选出的数字其和为 j 的方案数目（没有价值表示）。 - 状态转移方程：
根据本题的要求，上述「0-1 背包问题」的状态转移方程（1）可修改为： - 初始化
最优解的背包问题中，有的题目要求 恰好装满背包时的最优解</font >，有的题目则要求 不超过背包容量时的最优解</font >。一种区别这两种问法的实现方法是在状态初始化的时候有所不同。
- 如果要求恰好装满背包，那么在初始化时 dp[i][0]=0，其它 dp[i][1,2,…,∗] 均设为 −∞。这是因为此时只有容量为 0 的背包可能被价值为 0 的 nothing “恰好装满”，而其它容量的背包均没有合法的解，属于未定义的状态。
- 如果只是要求不超过背包容量而使得背包中的物品价值尽量大，初始化时应将 dp[∗][∗] 全部设为 0。这是因为对应于任何一个背包，都有一个合法解为 “什么都不装”，价值为 0
本题中，构造dp二维数组时，其维度为[neg+1,n+1]，即第一行可以为0个物品，则初始化为：
dp[0][0]=1：表示从前 0 个数字中选出若干个数字使得其和为 0 的方案数为 1，即「空集合」不选任何数字即可得到 0。- 对于其他
dp[0][j],j≥1，则有dp[0][j]=0：「空集合」无法选出任何数字使得其和为j≥1。
class Solution(object): |
2.3.2.3 一维数组
在状态转移过程中，每一行的 dp 状态值都只与其正上方和左上方的状态值有关，即dp[j]=dp[j]+dp[j-nums[i-1]]
考虑到我我们在更新 dp[j] 时，使用的其实是上一行的 dp 值；而如果第二层循环从小到大计算的话，那么 dp[j−nums[i−1]] 先于 dp[j] 被更新，因此当我们计算 dp[j] 值的时候，dp[j−nums[i−1]] 已经是被更新过的状态，而不再是上一行的 dp 值了。
而在第二层循环中，通过从大到小倒序计算则可巧妙地保证在计算 dp[j] 时所用到的 dp[j] 和 dp[j−nums[i−1]] 均来自上一行。
class Solution(object): |
等同于：
for num in nums: |
2.3.3 最后一块石头的重量 II （最大背包价值）
有一堆石头，用整数数组 stones 表示，其中 stones[i] 表示第 i 块石头的重量。每一回合，从石头中选出任意两块石头，将这两块石头一起粉碎。假设石头的重量分别为 x 和 y。且 x ≤ y，则结果如下：
- 如果
x == y，则两块石头都会被完全粉碎； - 如果
x < y，则重量为 x 的石头被完全粉碎，而重量为y的石头新重量为y - x。 - 最后，最多只会剩下一块石头，返回此石头的最小可能重量。如果没有石头剩下，则返回
0。
解题思路
选取两块石头，重新放回去的重量是两块石头的差值绝对值。重新放回去的石头还会进行选取，然后进行粉碎，直到最后只剩一块或者不剩石头。
这个问题其实可以转化为：把一堆石头尽量平均的分成两对，求两堆石头重量差的最小值。这就和「 0416. 分割等和子集」有点相似。两堆石头的重量要尽可能的接近数组总数量和的一半。
进一步可以变为：假设石头总重量和为 sum，则问题为将一堆石头放进容量最多为 sum / 2 的背包中，获得的最大价值为 max_weight（即其中一堆石子的重量），则另一堆石子的重量为 sum - max_weight。则两者的差值为 sum - 2 * max_weight，即为答案。
2.3.3.1 二维dp解法：遍历物品数=n+1
二维dp数组，第一行表示没有物品，则遍历物品数为物品数+1（n+1），此时数组全部初始化为 0即可：class Solution(object):
def lastStoneWeightII(self, stones):
"""
:type stones: List[int]
:rtype: int
"""
weight=sum(stones)//2
n=len(stones)
dp=[[0]*(weight+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(weight+1):
if j<stones[i-1]:
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])
return sum(stones)-2*dp[n][weight]
2.3.3.2 二维dp解法：遍历物品数=n
class Solution(object): |
2.3.3.3 一维dp解法：遍历物品数=n
class Solution(object): |
等同于：
for num in stones: |
三、 完全背包问题
参考：
- 【资料】背包九讲 - 崔添翼
- 【文章】背包 DP - OI Wiki
- 【文章】背包问题 第四讲 - 宫水三叶的刷题日记
- 【题解】『 套用完全背包模板 』详解完全背包（含数学推导） - 完全平方数 - 力扣
- 【题解】『 一文搞懂完全背包问题 』从0-1背包到完全背包，逐层深入+推导 - 零钱兑换 - 力扣
- 完全背包问题：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$，价值为 $value[i]$，每种物品数量没有限制。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
- 完全背包问题的特点：每种物品有无限件。
3.1 基础思路：二维数组（三重循环）
我们可以参考「0-1 背包问题」的状态定义和基本思路，对于容量为 $w$ 的背包，最多可以装 $\frac{w}{weight[i - 1]}$ 件第 $i - 1$ 件物品。那么我们可以多加一层循环，枚举第 $i - 1$ 件物品可以选择的件数（$0 \sim \frac{w}{weight[i - 1]}$），从而将「完全背包问题」转换为「0-1 背包问题」。
划分阶段
按照物品种类的序号、当前背包的载重上限进行阶段划分。- 定义状态
- 定义状态 $dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。
- 状态 $dp[i][w]$ 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。
- 定义状态
状态转移方程
由于每种物品可选的数量没有限制，因此状态 $dp[i][w]$ 可能从以下方案中选择最大值：- 选择 $0$ 件第 $i - 1$ 件物品：可以获得的最大价值为 $dp[i - 1][w]$
- 选择 $1$ 件第 $i - 1$ 件物品：可以获得的最大价值为 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$。
- 选择 $2$ 件第 $i - 1$ 件物品：可以获得的最大价值为 $dp[i - 1][w - 2 \times weight[i - 1]] + 2 \times value[i - 1]$。
- ……
- 选择 $k$ 件第 $i - 1$ 件物品：可以获得的最大价值为 $dp[i - 1][w - k \times weight[i - 1]] + k \times value[i - 1]$。
注意：选择 $k$ 件第 $i - 1$ 件物品的条件是 $0 \le k \times weight[i - 1] \le w$。
则状态转移方程为：
初始条件
- 如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[i][0] = 0$。
- 前 $0$ 种物品所能获得的最大价值一定为 $0$，即 $dp[0][w] = 0$。
最终结果
根据我们之前定义的状态，$dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[size][W]$，其中 $size$ 为物品的种类数，$W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W \times \sum\frac{W}{weight[i]})$，其中 $n$ 为物品种类数量，$W$ 为背包的载重上限，$weight[i]$ 是第 $i$ 种物品的重量。
- 空间复杂度：$O(n \times W)$。
3.2 状态转移方程优化（两重循环）
1. 优化思路
之前的思路中，对于每种物品而言，每次我们都需要枚举所有可行的物品数目 $k$，这就大大增加了时间复杂度。实际上，我们可以对之前的状态转移方程进行一些优化，从而减少一下算法的时间复杂度。
我们将之前的状态转移方程
进行展开：
而对于 $dp[i][w - weight[i - 1]]$ 我们有：
通过观察可以发现：
- $(1)$ 式中共有 $k + 1$ 项，$(2)$ 式中共有 $k$ 项；
- $(2)$ 式整个式子与 $(1)$ 式第 $1 \sim k + 1$ 项刚好相差一个 $value[i - 1]$。
则我们将 $(2)$ 式加上 $value[i - 1]$，再代入 $(1)$ 式中，可得到简化后的「状态转移方程」为：
简化后的「状态转移方程」去除了对物品件数的依赖，也就不需要遍历 $k$ 了，三层循环降为了两层循环。
注意：式 $(3)$ 的满足条件为 $0 \le weight[i - 1] \le w$。当 $w < weight[i - 1]$ 时，$dp[i][w] = dp[i - 1][w]$。
则状态转移方程为：
从上述状态转移方程我们可以看出：该式子与 0-1 背包问题中「思路 1」的状态转移式极其相似, 唯一区别点在于：
1. 0-1 背包问题中状态为 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$，这是第 $i - 1$ 阶段上的状态值。
2. 完全背包问题中状态为 $dp[i][w - weight[i - 1]] + value[i - 1]$，这是第 $i$ 阶段上的状态值。
2. 解题步骤
划分阶段
按照物品种类的序号、当前背包的载重上限进行阶段划分。- 定义状态
- 定义状态 $dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。
- 状态 $dp[i][w]$ 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。
- 定义状态
状态转移方程
初始条件
- 如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[i][0] = 0$。
- 前 $0$ 种物品所能获得的最大价值一定为 $0$，即 $dp[0][w] = 0$。
最终结果
根据我们之前定义的状态，$dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[size][W]$，其中 $size$ 为物品的种类数，$W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W)$，其中 $n$ 为物品种类数量，$W$ 为背包的载重上限。
- 空间复杂度：$O(n \times W)$。
3.3 滚动数组优化：一维数组
通过观察「思路 2」中的状态转移方程
可以看出：我们只用到了当前行（第 $i$ 行）的 $dp[i][w]$、$dp[i][w - weight[i - 1]]$，以及上一行（第 $i - 1$ 行）的 $dp[i - 1][w]$。
所以我们没必要保存所有阶段的状态，只需要使用一个一维数组 $dp[w]$ 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化（去掉动态规划状态的第一维）。
下面是具体的解题步骤：
划分阶段
按照当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。状态转移方程
注意：这里的 $dp[w - weight[i - 1]]$ 是第 $i$ 轮计算之后的「第 $i$ 阶段的状态值」。
因为在计算 $dp[w]$ 时，我们需要用到第 $i$ 轮计算之后的 $dp[w - weight[i - 1]]$，所以我们需要按照「从 $0 \sim W$ 正序递推的方式」递推 $dp[w]$，这样才能得到正确的结果。
因为 $w < weight[i - 1]$ 时，$dp[w]$ 只能取上一阶段的 $dp[w]$，其值相当于没有变化，这部分可以不做处理。所以我们在正序递推 $dp[w]$ 时，只需从 $weight[i - 1]$ 开始遍历即可。
初始条件
如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[0] = 0$。最终结果
根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。
class Solution: |
通过观察「0-1 背包问题滚动数组优化的代码」和「完全背包问题滚动数组优化的代码」可以看出，两者的唯一区别在于：
1. 0-1 背包问题滚动数组优化的代码采用了「从 $W \sim weight[i - 1]$ 逆序递推的方式」。
2. 完全背包问题滚动数组优化的代码采用了「从 $weight[i - 1] \sim W$ 正序递推的方式」。
- 时间复杂度：$O(n \times W)$，其中 $n$ 为物品种类数量，$W$ 为背包的载重上限。
- 空间复杂度：$O(W)$。
3.4 多重背包应用
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0279 | 完全平方数 | Python | 广度优先搜索、数学、动态规划 | 中等 |
| 0322 | 零钱兑换 | Python | 动态规划 | 中等 |
| 0518 | 零钱兑换 II | Python | 数组、动态规划 | 中等 |
| 0139 | 单词拆分 | Python | 字典树、记忆化搜索、哈希表、字符串、动态规划 | 中等 |
| 0377 | 组合总和 Ⅳ | Python | 数组、动态规划 | 中等 |
| 0638 | 大礼包 | |||
| 1449 | 数位成本和为目标值的最大数字 |
3.4.1 应用：零钱兑换
给定代表不同面额的硬币数组 coins 和一个总金额 amount，求出凑成总金额所需的最少的硬币个数。如果无法凑出，则返回 -1。
说明：
- $1 \le coins.length \le 12$。
- $1 \le coins[i] \le 2^{31} - 1$。
- $0 \le amount \le 10^4$。
示例：
输入：coins = [1, 2, 5], amount = 11 |
思路 1：完全背包问题
这道题可以转换为：有 $n$ 种不同的硬币，$coins[i]$ 表示第 $i$ 种硬币的面额，每种硬币可以无限次使用。请问凑成总金额为 $amount$ 的背包，最少需要多少硬币？
与普通完全背包问题不同的是，这里求解的是最少硬币数量。我们可以改变一下「状态定义」和「状态转移方程」。
划分阶段
按照当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[c]$ 表示为：凑成总金额为 $c$ 的最少硬币数量。状态转移方程
$dp[c] = \begin{cases} dp[c] & c < coins[i - 1] \cr min \lbrace dp[c], dp[c - coins[i - 1]] + 1 \rbrace & c \ge coins[i - 1] \end{cases}$- 当 $c < coins[i - 1]$ 时：
- 不使用第 $i - 1$ 枚硬币，只使用前 $i - 1$ 枚硬币凑成金额 $w$ 的最少硬币数量，即 $dp[c]$。
- 当 $c \ge coins[i - 1]$ 时，取下面两种情况中的较小值：
- 不使用第 $i - 1$ 枚硬币，只使用前 $i - 1$ 枚硬币凑成金额 $w$ 的最少硬币数量，即 $dp[c]$。
- 凑成金额 $c - coins[i - 1]$ 的最少硬币数量，再加上当前硬币的数量 $1$，即 $dp[c - coins[i - 1]] + 1$。
- 当 $c < coins[i - 1]$ 时：
初始条件
凑成总金额为 $0$ 的最少硬币数量为 $0$，即 $dp[0] = 0$。最终结果
根据我们之前定义的状态，$dp[c]$ 表示为：凑成总金额为 $c$ 的最少硬币数量。则最终结果为 $dp[amount]$。
class Solution: |
等同于
for coin in coins: |
- 时间复杂度：$O(amount \times size)$。其中 $amount$ 表示总金额，$size$ 表示硬币的种类数。
- 空间复杂度：$O(amount)$。
3.4.2 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
- 假设每一种面额的硬币有无限个。
- 题目数据保证结果符合 32 位带符号整数。
此题可参考494 目标和，唯一不同的是前者是0-1背包，本题是完全背包。
3.4.2.1 二维dp数组
class Solution(object): |
此题和494 目标和代码不同之处，是dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]，而非dp[i][j]=dp[i-1][j]+dp[i-][j-coins[i-1]]
1. 0-1 背包问题中状态为 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$，这是第 $i - 1$ 阶段上的状态值。
2. 完全背包问题中状态为 $dp[i][w - weight[i - 1]] + value[i - 1]$，这是第 $i$ 阶段上的状态值。
3.4.2.2 一维dp数组
动态规划的状态 dp[i] 可以表示为：凑成总金额为 i 的组合数。
动态规划的状态转移方程为：dp[i] = dp[i] + dp[i - coin]，意思为凑成总金额为 i 的组合数 = 「不使用当前 coin，只使用之前硬币凑成金额 i 的组合数」+「使用当前 coin 凑成金额 i - coin 的方案数」。class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
size=len(coins)
# 一维dp数组，dp[w]表示装满w的背包最少需要多少硬币，dp[0]=1
size = len(coins)
dp = [0 for _ in range(amount + 1)]
dp[0] = 1
# 枚举前 i 种物品
for coin in coins:
# 正序枚举背包装载重量
for j in range(coin, amount + 1):
dp[j] = dp[j]+dp[j - coin]
return dp[amount]
1. 0-1 背包问题滚动数组优化的代码采用了「从 $W \sim weight[i - 1]$ 逆序递推的方式」。
2. 完全背包问题滚动数组优化的代码采用了「从 $weight[i - 1] \sim W$ 正序递推的方式」。
3.4.3 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例：输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合
由于需要考虑选取元素的顺序，因此这道题需要计算的是选取元素的排列数。
定义
用 dp[x] 表示选取的元素之和等于 x 的方案数，目标是求 dp[target]。初始化
动态规划的边界是 dp[0]=1。只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
class Solution(object): |
3.5 总结:一种规律搞定背包问题
背包问题技巧：常见的背包问题有组合问题、True/False问题、最大最小问题。
- 如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums: |
- 如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums: |
- 如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1): |
四、 多重背包问题
参考
- 【资料】背包九讲 - 崔添翼
- 【文章】背包 DP - OI Wiki
- 【文章】【动态规划/背包问题】多重背包の二进制优化
多重背包问题：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$，价值为 $value[i]$，件数为 $count[i]$。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
4.1 多重背包问题基本思路
我们可以参考「0-1 背包问题」的状态定义和基本思路，对于容量为 $w$ 的背包，最多可以装 $min \lbrace count[i - 1]，\frac{w}{weight[i - 1]} \rbrace$ 件第 $i - 1$ 件物品。那么我们可以多加一层循环，枚举第 $i - 1$ 件物品可以选择的件数（$0 \sim min \lbrace count[i - 1]，\frac{w}{weight[i - 1]} \rbrace$），从而将「完全背包问题」转换为「0-1 背包问题」。
思路 1：动态规划 + 二维基本思路
划分阶段
按照物品种类的序号、当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。
状态 $dp[i][w]$ 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。
状态转移方程
$dp[i][w] = max \lbrace dp[i - 1][w - k \times weight[i - 1]] + k \times value[i - 1] \rbrace，\quad 0 \le k \le min \lbrace count[i - 1]，\frac{w}{weight[i - 1]} \rbrace$。初始条件
- 如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[i][0] = 0$。
- 前 $0$ 种物品所能获得的最大价值一定为 $0$，即 $dp[0][w] = 0$。
最终结果
根据我们之前定义的状态，$dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[size][W]$，其中 $size$ 为物品的种类数，$W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W \times \sum count[i])$，其中 $n$ 为物品种类数量，$W$ 为背包的载重上限，$count[i]$ 是第 $i$ 种物品的重量。
- 空间复杂度：$O(n \times W)$。
4.2 多重背包问题滚动数组优化
在「完全背包问题」中，我们通过优化「状态转移方程」的方式，成功去除了对物品件数 $k$ 的依赖，从而将时间复杂度下降了一个维度。
而在「多重背包问题」中，我们在递推 $dp[i][w]$ 时，是无法从 $dp[i][w - weight[i - 1]]$ 状态得知目前究竟已经使用了多个件第 $i - 1$ 种物品，也就无法判断第 $i - 1$ 种物品是否还有剩余数量可选。这就导致了我们无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。
但是我们可以参考「完全背包问题」+「滚动数组优化」的方式，将算法的空间复杂度下降一个维度。
思路 2：动态规划 + 滚动数组优化
划分阶段
按照当前背包的载重上限进行阶段划分。- 定义状态
定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。
- 定义状态
状态转移方程
$dp[w] = max \lbrace dp[w - k \times weight[i - 1]] + k \times value[i - 1] \rbrace , \quad 0 \le k \le min \lbrace count[i - 1]，\frac{w}{weight[i - 1]} \rbrace$初始条件
如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[0] = 0$。最终结果
根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(n \times W \times C)$，其中 $n$ 为物品种类数量，$W$ 为背包的载重上限，$C$ 是物品的数量数组长度。因为 $n \times C = \sum count[i]$，所以时间复杂度也可以写成 $O(W \times \sum count[i])$。
- 空间复杂度：$O(W)$。
4.3 多重背包问题二进制优化
在「思路 2」中，我们通过「滚动数组优化」的方式，降低了算法的空间复杂度。同时也提到了无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。
但我们还是可以从物品数量入手，通过「二进制优化」的方式，将算法的时间复杂度降低。
二进制优化：简单来说，就是把物品的数量 $count[i]$ 拆分成「由 $1、2、4、…、2^m$ 件单个物品组成的大物品」，以及「剩余不足 $2$ 的整数次幂数量的物品，由 $count[i] -2^{\lfloor \log_2(count[i] + 1) \rfloor - 1}$ 件单个物品组成大物品」。
举个例子，第 $i$ 件物品的数量为 $31$，采用「二进制优化」的方式，可以拆分成 $31 = 1 + 2 + 4 + 8 + 16$ 一共 $5$ 件物品。也将是将 $31$ 件物品分成了 $5$ 件大物品：
- 第 $1$ 件大物品有 $1$ 件第 $i$ 种物品组成；
- 第 $2$ 件大物品有 $2$ 件第 $i$ 种物品组成；
- 第 $3$ 件大物品有 $4$ 件第 $i$ 种物品组成；
- 第 $4$ 件大物品有 $8$ 件第 $i$ 种物品组成；
- 第 $5$ 件大物品有 $16$ 件第 $i$ 种物品组成。
这 5 件大物品通过不同的组合，可表达出第 $i$ 种物品的数量范围刚好是 0 ~31。这样本来第 i件物品数量需要枚举共计 32 次（$0 \sim 31$），而现在只需要枚举 5 次即可。
再举几个例子：
- 第 $i$ 件物品的数量为 $6$，可以拆分为 $6 = 1 + 2 + 3$ 一共 $3$ 件物品。
- 第 $i$ 件物品的数量为 $8$，可以拆分为 $8 = 1 + 2 + 4 + 1$ 一共 $4$ 件物品。
- 第 $i$ 件物品的数量为 $18$，可以拆分为 $18 = 1 + 2 + 4 + 8 + 3$ 一共 $5$ 件物品。
经过「二进制优化」之后，算法的时间复杂度从 $O(W \times \sum count[i])$ 降到了 $O(W \times \sum \log_2{count[i]})$。
思路 3：动态规划 + 二进制优化
划分阶段
按照当前背包的载重上限进行阶段划分。定义状态
定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。状态转移方程
$dp[w] = max \lbrace dp[w - weight \underline{ } new[i - 1]] + value \underline{ } new[i - 1] \rbrace$初始条件
如果背包容量为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dp[0] = 0$。最终结果
根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。
class Solution: |
- 时间复杂度：$O(W \times \sum \log_2{count[i]})$，其中 $W$ 为背包的载重上限，$count[i]$ 是第 $i$ 种物品的数量。
- 空间复杂度：$O(W)$。
4.4 多重背包问题应用
五、 分组背包问题应用
分组背包问题：有 $n$ 组物品和一个最多能装重量为 $W$ 的背包，第 $i$ 组物品的件数为 $count[i]$，第 $i$ 组的第 $j$ 个物品重量为 $weight[i][j]$，价值为 $value[i][j]$。每组物品中最多只能选择 $1$ 件物品装入背包。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1155 | 掷骰子的N种方法 | |||
| 2585 | 获得分数的方法数 |