背包问题type
status
date
slug
summary
tags
category
icon
password
Property
背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？
根据物品限制条件的不同，背包问题可分为：0-1 背包问题、完全背包问题、多重背包问题、分组背包问题，以及混合背包问题等。
背包问题的暴力解题：假设有件物品，枚举出这件物品所有可能的组合。然后再判断这些组合中的物品是否能放入背包，以及是否能得到最大价值。这种做法的时间复杂度是，复杂度是指数级别的，可以利用动态规划算法减少一下时间复杂度。
0-1背包问题
0-1 背包问题：有件物品和有一个最多能装重量为的背包。第件物品的重量为，价值为，每件物品有且只有件。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
0-1 背包问题的特点：每种物品有且仅有件，可以选择不放入背包，也可以选择放入背包。
基本思路
- 划分阶段：按照物品的序号、当前背包的载重上限进行阶段划分
- 定义状态
定义状态 表示为：前件物品放入一个最多能装重量为的背包中，可以获得的最大价值。 是一个二维数组，第一维代表「当前正在考虑的物品」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。
- 状态转移方程
- 第 件物品不放入背包：问题转换为「前 件物品放入一个最多能装重量为 的背包中 ，可以获得的最大价值」为 。
- 第 件物品放入背包：问题转换为「前 件物品放入一个最多能装重量为 的背包中，可以获得的最大价值」为 ，再加上「放入的第 件物品的价值」为 ，则此时可以获得的最大价值为 。
- 如果当前背包的载重不足时（）：第 件物品一定不能放入背包，此时背包的价值仍为 时的价值，即
- 如果当前背包的载重足够时（即 ）：第 件物品可以考虑放入背包，或者不放入背包，此时背包的价值取两种情况下的最大值，即
对于「将前 件物品放入一个最多能装重量为 的背包中，可以获得的最大价值 」这个子问题，如果只考虑第 件物品（前件物品中最后一件物品）的放入策略（放入背包和不放入背包两种策略）。则问题可以转换为一个只跟前 件物品相关的问题。
考虑一下第 件物品满足什么条件时才能考虑是否放入背包，并且在什么条件下一定不能放入背包。
状态转移方程为：
- 初始条件
- 如果背包载重上限为，则无论选取什么物品，可以获得的最大价值一定是 ，即
- 无论背包载重上限是多少，前件物品所能获得的最大价值一定为 ，即
时间复杂度： ，为物品数量，为背包的载重上限
空间复杂度：
滚动数组优化
根据之前的求解过程可以看出：当依次处理前 件物品时，「前 件物品的处理结果」只跟「前 件物品的处理结果」，跟之前更早的处理结果没有太大关系。也就是说在状态转移的过程中，只用到了当前行（第 行）的 以及上一行（第 行）的 、 。
所以没必要保存所有阶段的状态，只需要保存上一阶段的所有状态和当前阶段的所有状态就可以了，这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了，用 保存原先 的状态，用 保存当前 的状态。还可以进一步进行优化，只需要使用一个一维数组 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化（去掉动态规划状态的第一维）。
定义状态 表示为：将物品装入最多能装重量为 的背包中，可以获得的最大价值。
状态转移方程：
在第 轮计算之前， 中保存的是「第 阶段的所有状态值」。在第 轮计算之后， 中保存的是「第 阶段的所有状态值」。
为了保证第 轮计算过程中， 是由第 轮中 和 两个状态递推而来的值，需要按照「从 逆序的方式」倒推 。
这是因为如果采用「从 正序递推的方式」递推 ，如果当前状态 已经更新为当前第 阶段的状态值。那么在向右遍历到 时，需要的是第 阶段的状态值（即上一阶段的 ），而此时 已经更新了，会破坏当前阶段的状态值，从而无法推出正确结果。
而如果按照「从 逆序的方式」倒推 则不会出现该问题。因为 时， 只能取上一阶段的 ，其值相当于没有变化，这部分可以不做处理。所以在逆序倒推 时，只需遍历到 时即可。
初始条件：无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 ，即
最终结果：
时间复杂度： 空间复杂度：
分割等和子集
题目：给你一个只包含正整数 的非空数组
nums。判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例：
换一种表述：给定一个只包含正整数的非空数组，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。这个问题可以转换成「0−1背包问题」，与传统的「0−1背包问题」的区别在于，传统的「0−1背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。
等价于，背包承重为
W=sum/2，各物品重量为w[i]=nums[i]，各物品价值为v[i]=nums[i]，在不超过承重W的前提下，求能装入背包的最大价值（当最大价值为sum/2时，说明有解）完全背包问题
完全背包问题：有 种物品和一个最多能装重量为 的背包，第 种物品的重量为 ，价值为 ，每种物品数量没有限制。在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
参考「0-1 背包问题」的状态定义和基本思路，对于容量为的背包，最多可以装 件第件物品。可以多加一层循环，枚举第件物品可以选择的件数（），将「完全背包问题」转换为「0-1 背包问题」。
基本思路
- 划分阶段：按照物品的序号、当前背包的载重上限进行阶段划分
- 定义状态 ：前件物品放入一个最多能装重量为的背包中，可以获得的最大价值。
- 状态转移方程
- 选择 件第 件物品：可以获得的最大价值为
- 选择 件第 件物品：可以获得的最大价值为
- 选择 件第 件物品：可以获得的最大价值为
- ……
- 选择 件第 件物品：可以获得的最大价值为
由于每种物品可选的数量没有限制，因此状态 可能从以下方案中选择最大值：
注意：选择 件第 件物品的条件是
则状态转移方程为：
- 初始条件
- 如果背包载重上限为 ，则无论选取什么物品，可以获得的最大价值一定是 ，。
- 无论背包载重上限是多少，前 件物品所能获得的最大价值一定为 ，。
时间复杂度： ，为物品种类数量 空间复杂度：
状态转移方程优化
对每种物品，每次枚举所有可行的物品数目 ，大大增加了时间复杂度。可以对之前的状态转移方程进行一些优化，从而减少一下算法的时间复杂度。将之前的状态转移方程
进行展开：
而对于 有：
可以发现：
- 式中共有 项， 式中共有 项
- 式整个式子与 式第 项刚好相差一个
将 式加上 ，再代入 式中，可得到简化后的「状态转移方程」为：
简化后的「状态转移方程」去除了对物品件数的依赖，也就不需要遍历 了，三层循环降为了两层循环。
则状态转移方程为：
从上述状态转移方程我们可以看出：该式子与 0-1 背包问题中「思路 1」的状态转移式极其相似。
唯一区别点在于：
- 0-1 背包问题中状态为 ，这是第 阶段上的状态值。
- 完全背包问题中状态为 ，这是第 阶段上的状态值。
时间复杂度： 空间复杂度：
滚动数组优化
通过观察中的状态转移方程
没必要保存所有阶段的状态，只需要使用一个一维数组 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化
定义状态 ：将物品装入最多能装重量为 的背包中，可以获得的最大价值。
状态转移方程：
这里的 是第 轮计算之后的「第 阶段的状态值」
因为在计算 时，需要用到第 轮计算之后的 ，所以需要按照「从 正序递推的方式」递推 ，这样才能得到正确的结果。
因为 时， 只能取上一阶段的 ，其值相当于没有变化，这部分可以不做处理。所以在正序递推 时，只需从 开始遍历即可。
初始条件:
通过观察「0-1 背包问题滚动数组优化的代码」和「完全背包问题滚动数组优化的代码」可以看出，两者的唯一区别在于：
- 0-1 背包问题滚动数组优化的代码采用了「从 逆序递推的方式」
- 完全背包问题滚动数组优化的代码采用了「从 正序递推的方式」
时间复杂度： 空间复杂度：
零钱兑换
题目：给你一个整数数组
coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。示例：
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
凑足总额为
j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]所以
dp[j] 要取所有dp[j - coins[i]] + 1中最小的。递推公式：
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);零钱兑换II
题目：给一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。请计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0 。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。示例：
单词拆分
题目：给一个字符串
s 和一个字符串列表 wordDict 作为字典。请判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。示例：
转化为是否可以用wordDict中的词组合成s，完全背包问题，并且为“考虑排列顺序的完全背包问题”，外层循环为target ，内层循环为选择池wordDict。 dp[i] 表示以 i 结尾的字符串是否可以被wordDict中组合而成。
- 外层遍历
s中每一个与word同长度的字串s.substr(i - sz, sz)；
- 内层遍历
wordDict每个word
判断
s.substr(i - sz, sz) == word： （1）若不相等，说明与该 word 不匹配，继续遍历； （2）若相等，说明从 [i - sz] 到 i 的字符与 word 匹配。 dp[i] = dp[i] || d[[i - sz]] 对于边界条件，定义
dp[0] = true表示空串且合法多重背包问题
多重背包问题：有 种物品和一个最多能装重量为 的背包，第 种物品的重量为 ，价值为 ，件数为 。在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
可以参考「0-1 背包问题」的状态定义和基本思路，对于容量为 的背包，最多可以装 件第 件物品。那么可以多加一层循环，枚举第 件物品可以选择的件数（），从而将「完全背包问题」转换为「0-1 背包问题」。
状态转移方程
时间复杂度： ，其中为物品种类数量， 为背包的载重上限， 是物品的数量数组长度。因为，所以时间复杂度也可以写成
空间复杂度：
滚动数组优化
在「完全背包问题」中，通过优化「状态转移方程」的方式，成功去除了对物品件数的依赖，将时间复杂度下降了一个维度。而在「多重背包问题」中，递推 时，是无法从 状态得知目前究竟已经使用了多个件第 种物品，也就无法判断第 种物品是否还有剩余数量可选。这就导致了无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。
但是可以参考「完全背包问题」+「滚动数组优化」的方式，将算法的空间复杂度下降一个维度。
定义状态 ：将物品装入最多能装重量为 的背包中，可以获得的最大价值。
状态转移方程：
初始条件：
时间复杂度： ，其中 为物品种类数量， 为背包的载重上限， 是物品的数量数组长度。因为，所以时间复杂度也可以写成
空间复杂度：
二进制优化
二进制优化：简单来说，就是把物品的数量 拆分成「由 件单个物品组成的大物品」，以及「剩余不足 的整数次幂数量的物品，由 件单个物品组成大物品」。
举个例子，第 件物品的数量为 ，采用「二进制优化」的方式，可以拆分成 一共 件物品。也将是将 件物品分成了 件大物品：
- 第 件大物品有 件第 种物品组成；
- 第 件大物品有 件第 种物品组成；
- 第 件大物品有 件第 种物品组成；
- 第 件大物品有 件第 种物品组成；
- 第 件大物品有 件第 种物品组成。
这 件大物品通过不同的组合，可表达出第 种物品的数量范围刚好是 。这样本来第 件物品数量需要枚举共计 次（ ），而现在只需要枚举 次即可。
经过「二进制优化」之后，算法的时间复杂度从 降到了。
定义状态 ：将物品装入最多能装重量为 的背包中，可以获得的最大价值。
状态转移方程：
初始条件：
时间复杂度： 空间复杂度：
混合背包问题
混合背包问题：有 种物品和一个最多能装重量为 的背包，第 种物品的重量为
weight[i]，价值为value[i]，件数为count[i]- 当
count[i]=−1时，代表该物品只有件
- 当
count[i]=0时，代表该物品有无限件
- 当
count[i]>0时，代表该物品有count[i]件
在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
混合背包问题其实就是将「0-1 背包问题」、「完全背包问题」和「多重背包问题」这 3 种背包问题综合起来，有的是能取 1 件，有的能取无数件，有的只能取
count[i]件。在「多重背包问题」中，使用「二进制优化」的方式，将「多重背包问题」转换为「0-1 背包问题」，那么在解决「混合背包问题」时，也可以先将「多重背包问题」转换为「0-1 背包问题」，然后直接再区分是「0-1 背包问题」还是「完全背包问题」就可以了。时间复杂度： 空间复杂度：
分组背包问题
分组背包问题：有 组物品和一个最多能装重量为 的背包，第组物品的件数为，第组的第个物品重量为，价值为。每组物品中最多只能选择 1 件物品装入背包。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
定义状态表示为：前组物品放入一个最多能装重量为 的背包中，可以获得的最大价值。
状态转移方程
由于可以不选择 组物品中的任何物品，也可以从第组物品的第 件物品中随意选择1件物品，所以状态可能从以下方案中选择最大值：
- 不选择第 组中的任何物品：可以获得的最大价值为
- 选择第 组物品中第 0 件：可以获得的最大价值为
- 选择第 组物品中第 1 件：可以获得的最大价值为
- ……
- 选择第 组物品中最后 1 件：假设 ，则可以获得的最大价值为
则状态转移方程为：
初始条件
时间复杂度： ， 是每组物品的数量，因为 ，所以也可以写成
空间复杂度：
滚动数组优化
定义状态 表示为：将物品装入最多能装重量为 的背包中，可以获得的最大价值
状态转移方程：
空间复杂度：
二维费用背包问题
二维费用背包问题：有件物品和有一个最多能装重量为、容量为的背包。第 件物品的重量为，体积为，价值为，每件物品有且只有1件。请问在总重量不超过背包载重上限、容量上限的情况下，能装入背包的最大价值是多少？
可以参考「0-1 背包问题」的状态定义和基本思路，在「0-1 背包问题」基本思路的基础上，增加一个维度用于表示物品的容量。
定义状态 ：前件物品放入一个最多能装重量为、容量为的背包中，可以获得的最大价值。
状态转移方程
初始条件：
时间复杂度： 空间复杂度：
滚动数组优化
定义状态 ：将物品装入最多能装重量为、容量为 的背包中，可以获得的最大价值
状态转移方程
初始条件：
时间复杂度： 空间复杂度：
背包问题变种
求恰好装满背包的最大价值
背包问题求恰好装满背包的最大价值：在给定背包重量 ，每件物品重量 ，物品间相互关系（分组、依赖等）的背包问题中，问在恰好装满背包的情况下，能装入背包的最大价值总和是多少？
在背包问题中，有的题目不要求把背包装满，而有的题目要求恰好装满背包。
如果题目要求「恰好装满背包」，则可在原有状态定义、状态转移方程的基础上，在初始化时，令 ，以及 。 这样就可以保证最终得到的为恰好装满背包的最大价值总和。
这是因为：初始化的 数组实际上就是在没有任何物品可以放入背包时的「合法状态」。
如果不要求恰好装满背包，那么：
- 任何载重上限下的背包，在不放入任何物品时，都有一个合法解，此时背包所含物品的最大价值为，即
而如果要求恰好装满背包，那么：
- 只有载重上限为 的背包，在不放入物品时，能够恰好装满背包（有合法解），此时背包所含物品的最大价值为 ，即
- 其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值应为，即
这样在进行状态转移时，可以通过判断与 的关系，来判断是否能恰好装满背包。
以「0-1 背包问题」求恰好装满背包的最大价值为例。
定义状态：定义状态 表示为：将物品装入一个最多能装重量为 的背包中，恰好装满背包的情况下，能装入背包的最大价值总和。
状态转移方程：
初始条件：
- 其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值应为 ，即
时间复杂度：，其中为物品种类数量，为背包的载重上限
空间复杂度：
求方案总数
背包问题求方案数：在给定背包重量 ，每件物品重量 ，物品间相互关系（分组、依赖等）的背包问题中，请问在总重量不超过背包载重上限的情况下，或者在总重量不超过某一指定重量的情况下，一共有多少种方案？
这种问题就是将原有状态转移方程中的「求最大值」变为「求和」即可。以「0-1 背包问题」求方案总数为例。
0-1 背包问题求方案数：有 件物品和有一个最多能装重量为的背包。第 件物品的重量为，价值为，每件物品有且只有件。问在总重量不超过背包载重上限的情况下，一共有多少种方案？
- 使用二维状态定义，可定义状态 为：前 件物品放入一个最多能装重量为 的背包中的方案总数。则状态转移方程为：
- 使用一维状态定义，可定义状态 表示为：将物品装入一个最多能装重量为 的背包中的方案总数。则状态转移方程为：
初始条件：如果背包载重上限为 ，则一共有 种方案（什么也不装），即
时间复杂度： 空间复杂度：
求最优方案数
背包问题求最优方案数：在给定背包重量 ，每件物品重量 、物品价值 ，物品间相互关系（分组、依赖等）的背包问题中，请问在总重量不超过背包载重上限的情况下，使背包总价值最大的方案数是多少？
通过结合「求背包最大可得价值」和「求方案数」两个问题的思路，可以分别定义两个状态：
- 定义 表示为：前 种物品放入一个最多能装重量为的背包中，可获得的最大价值
- 定义 表示为：前 种物品放入一个最多能装重量为的背包中，使背包总价值最大的方案数
以「0-1 背包问题」求最优方案数为例。
0-1 背包问题求最优方案数：有 种物品和一个最多能装重量为 的背包，第 种物品的重量为，价值为，每件物品有且只有件。问在总重量不超过背包载重上限的情况下，使背包总价值最大的方案数是多少？
定义状态：
- 定义 表示为：前 种物品放入一个最多能装重量为 的背包中，可获得的最大价值。
- 定义 表示为：前 种物品放入一个最多能装重量为 的背包中，使背包总价值最大的方案数。
状态转移方程：
- 如果 ，则说明选择第 件物品获得价值更高，此时方案数 是在 基础上添加了第 件物品，因此方案数不变，即： 。
- 如果 ，则说明选择与不选择第 件物品获得价格相等，此时方案数应为两者之和，即： 。
- 如果 ，则说明不选择第 件物品获得价值更高，此时方案数等于之前方案数，即：
初始条件：
最终结果： 表示为：前 种物品放入一个最多能装重量为 的背包中，使背包总价值最大的方案数。则最终结果为 ，其中 为物品的种类数， 为背包的载重上限。
时间复杂度： 空间复杂度：
求具体方案
背包问题求具体方案：在给定背包重量 ，每件物品重量 、物品价值 ，物品间相互关系（分组、依赖等）的背包问题中，请问将哪些物品装入背包，可使这些物品的总重量不超过背包载重上限，且价值总和最大？
一般背包问题都是求解一个最优值，但是如果要输出该最优值的具体方案，除了 ，可以再定义一个数组 用于记录状态转移时，所取的状态是状态转移方程中的哪一项，从而确定选择的具体物品。
以「0-1 背包问题」求具体方案为例。
0-1 背包问题求具体方案：有 种物品和一个最多能装重量为 的背包，第 种物品的重量为 ，价值为 ，每件物品有且只有 件。请问将哪些物品装入背包，可使这些物品的总重量不超过背包载重上限，且价值总和最大？
0-1 背包问题的状态转移方程为：
可以再定义一个 用于记录状态转移时，所取的状态是状态转移方程中的哪一项。
- 如果 ，说明：转移到 时，选择了前一项 ，并且具体方案中不包括第 件物品。
- 如果 ，说明：转移到 时，选择了后一项 ，并且具体方案中包括第 件物品。
时间复杂度： 空间复杂度：
求字典序最小的具体方案
这里的「字典序最小」指的是序号为 的物品选择方案排列出来之后的字典序最小。
仍以「0-1 背包问题」求字典序最小的具体方案为例。
为了使「字典序最小」。可以先将物品的序号进行反转，从 变为 ，然后在返回具体方案时，再根据 将序号变回来。
这是为了在选择物品时，尽可能的向后选择反转后序号大的物品（即原序号小的物品），从而保证原序号为 的物品选择方案排列出来之后的字典序最小。
时间复杂度： ，其中为物品种类数量，为背包的载重上限 空间复杂度：