-
概念：一共有 N 件物品，第
i（ i 从 0 开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？ -
思路：定义一个二维数组
dp存储最大价值，其中dp[i][j]表示前i件物品体积不超过j的情况下能达到的最大价值。设第i件物品体积为w，价值为v，根据第i件物品是否添加到背包中，可以分两种情况讨论：- 第
i件物品没添加到背包，总体积不超过j的前i件物品的最大价值就是总体积不超过j的前i-1件物品的最大价值，$dp[i][j] = dp[i-1][j]$ - 第
i件物品添加到背包中，$dp[i][j] = dp[i-1][j-w[i]] + v[i]$
- 第
-
状态转换方程：$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) , j >= w[i]$
-
源代码：
// N, mxW 分别表示物体数量以及背包总体积 // weights[i], values[i] 分别表示物体的重量以及物体的价值 // 二维 DP int backpack(int w, vector<int> &weights, vector<int> &values) { vector<vector<int>> dp(N+1, vector<int>(w+1, 0)) for(int i = 1; i <= N; ++ i) { int w = weights[i - 1], v = values[i - 1]; for (int j = 1; j <= mxW; ++ j) { if (j >= w) { // 背包承受力足够放下第 i 个物体 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v); } else { // 背包承受力不够放下第 i 个物体 dp[i][j] = dp[i-1][j]; } } } return dp[N][w]; } // 一维DP void test_1_wei_bag_problem() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector<int> dp(bagWeight + 1, 0); 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]); } } cout << dp[bagWeight] << endl; }
最后优化一下空间的写法需要思考，这里不细说了，注意第二个循环需要倒序遍历，具体参考：
关于 for 循坏嵌套顺序，二维 DP 中先遍历物品或者先遍历背包容量都可以，一维 DP 中只能先遍历物品，关键在于其背包容量需要倒序遍历防止多次选择某个物品
0-1背包一般是最大最小问题
-
概念：和 0-1背包问题相似，只是每个重量的物体有无数多个，也就可以重复放某个价值的物体，最终目的就是让背包的总价值最大
-
思路：总体思想和 0-1 背包一样
- 第
i件物品没添加到背包，同上，$dp[i][j] = dp[i-1][j]$ - 第
i件物品添加到背包中，此时和 0-1 背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第 i 种商品后还可以再继续装入第 i 种商品。$dp[i][j] = dp[i][j-w[i]] + v[i]$
- 第
-
状态转换方程：$dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i]) , j >= w[i]$
-
源代码：
// 二维DP，同上，只是状态转移方程不是 dp[i-1][j-w] 而是 dp[i][j-w] if (j >= w) { dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v); } else { dp[i][j] = dp[i-1][j]; } // 先遍历物品，在遍历背包，不同问题需要注意顺序，见下LC实战 // 一维DP void test_CompletePack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight] << endl; }
同理可以优化空间，需要注意：第二个循环必须正序遍历，具体参考
关于嵌套顺序，不管是一维还是二维，普通完全背包问题中先遍历物品还是先遍历背包容量都是可以的
有 N 种物品和一个容量为 V 的背包。第i种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
如下图：物品0有 2 个，物品1有 3 个，物品2有 2 个
| 重量 | 价值 | 数量 | |
|---|---|---|---|
| 物品0 | 1 | 15 | 1 |
| 物品0 | 1 | 15 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品2 | 4 | 30 | 1 |
| 物品2 | 4 | 30 | 1 |
所以只需要将 values 数组和 weight 数组转换成 0-1 背包就可以了
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
vector<int> nums = {2, 3, 2};
int bagWeight = 10;
for (int i = 0; i < nums.size(); i++) {
while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
weight.push_back(weight[i]);
value.push_back(value[i]);
nums[i]--;
}
}
// 之后就可以按照 0-1 背包问题求解了，代码同上太难了，🤮了，具体可以参考九讲背包问题
| 题目 | 说明 | 题解 |
|---|---|---|
| 494. 目标和 | 0-1背包变形，转化背包容量恰好等于 (target + sum(nums))/2，注意一维和二维写法，记忆化搜索 | 0x3F |
| 518. 零钱兑换 II | 完全背包，组合问题，一维DP需要先物体在容量，二维DP都可以 🔥 | Carl |
| 377. 组合总和 Ⅳ | 完全背包，排列问题，一维DP需要先容量再物体，二维DP很复杂!!! | 二维DP |
| 2572. 无平方子集计数 | 首先预处理所有无平方因子数成质因子集合mask，然后枚举子集的乘积，将乘积看成背包容量，有点难，和一般的0-1背包不太一样 | 0x3F |
// 此类问题一维DP的基础模板
// 1. 如果求组合数就是外层for循环遍历物品，内层for遍历背包【不强调顺序】
// 2. 如果求排列数就是外层for遍历背包，内层for循环遍历物品【强调顺序】
// 注意初始化，一般 dp(target+1, 0), dp[0]=1
dp[i] += dp[i-num]原题LC.70 是一个比较简单的DP问题，但是如果将题目改为：一步一个台阶，两个台阶，三个台阶，......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？ 那就是一个完全背包问题了，1、2、3...阶是物体，楼顶是背包，每一阶可以重复使用，就是 LC.377 一样了，考虑顺序
这里展示一下 377.组合总和 Ⅳ 的思路，需要考虑顺序问题
- 用
dp[x]表示选取的元素之和等于x的方案数，目标是求dp[target] - 动态规划的边界是
dp[0]=1，有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。 - 当
1 <= i <= target，如果存在一种排列，其中的元素之和等于i，则该排列的最后一个元素一定是数组 nums 中的一个元素，假设该排列的最后一个元素是 num，则一定有num <= i，对于元素之和等于i−num的每一种排列，在最后添加num之后即可得到一个元素之和等于i的排列，因此在计算dp[i]时，应该计算所有的dp[i−num]之和。 - 参考：评论思路
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned long long> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; ++ i) {
for (auto num: nums) {
if (i >= num ) dp[i] += dp[i-num];
}
}
return dp[target];
}说明一下：这里使用 unsigned long long 是为了防止测试数据的溢出，其实这个测试用例有点内个，我的疑问解答
| 题目 | 说明 | 题解 |
|---|---|---|
| 474. 一和零 | 0-1 背包，最大问题，一维DP注意倒叙，二维DP也可以 | liweiwei |
| 322. 零钱兑换 | 完全背包，最小问题，一维DP两种遍历方式都可以 🔥 记忆化搜索 | 0x3F |
| 279. 完全平方数 | 完全背包，最小问题，注意初始化，dp(n+1, INT_MAX), dp[0]=0 | carl |
// 最大最小问题一般模板
// 1. 此类问题两层for循环的先后顺序无所谓
// 2. 注意初始化，一般是 dp(n+1, INT_MAX), dp[0]=0
dp[i] = min(dp[i], dp[i-num]+1)
dp[i] = max(dp[i], dp[i-num]+1)这里展示 LC.322 的题解，参考：力扣-江不知
-
假设
f(n)代表要凑齐金额为 n 所要用的最少硬币数量，那么有：$f(n) = min(f(n - c_1), f(n - c_2), ... f(n - c_{n})) + 1$ 其中
c1 ~ cn为硬币的所有面额。 -
再具体解释一下这个公式吧，例如这个示例：
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
题目求的值为
f(11)，第一次选择硬币时我们有三种选择。假设我们取面额为 1 的硬币，那么接下来需要凑齐的总金额变为
11 - 1 = 10，即f(11) = f(10) + 1，这里的+1就是我们取出的面额为 1 的硬币。同理，如果取面额为 2 或面额为 5 的硬币可以得到：
f(11) = f(9) + 1f(11) = f(6) + 1
所以：
f(11) = min(f(10), f(9), f(6)) + 1 -
代码注意：本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！关于遍历顺序的解读
| 题目 | 说明 | 题解 |
|---|---|---|
| 416. 分割等和子集 | 0-1背包，转换成 dp[i] 表示 nums 中存在和为 i 的子集，容量为 sum/2 | 通过 |
| 139. 单词拆分 | 完全背包，有顺序，dp[i] 表示前i个字符是否可以由字典表示 | 通过 |
// True or False 问题的一般模板
// 1. 一般初始化 dp[0] = true
// 2. 完全背包注意遍历物品和容量的先后顺序，0-1背包注意遍历容量逆序
dp[i] = dp[i] || dp[i-num]这里展示139.单词拆分：
dp[i]表示s的前i位是否可以用wordDict中的单词表示
- dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。
- 该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.length();
bool dp[n + 1]; memset(dp, 0, sizeof dp);
dp[0] = true;
// 有顺序的完全背包问题
for (int i = 1; i <= n; i++) {
for (auto& word : wordDict) { // 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word == s.substr(i-len, len)) {
dp[i] = dp[i] || dp[i - len];
if (dp[i]) break;
}
}
}
return dp[n];
}另外还有一种不太往背包问题上靠的解法：
bool wordBreak(string s, vector<string>& wordDict) {
// dp[i] 表示 s 的前 i 个字符是否可以由 wordDict 表示
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
// 转成红黑树方便查找
unordered_set<string> st(wordDict.begin(), wordDict.end());
int maxLen = 0, minLen = INT_MAX;
for (auto& word: wordDict) {
maxLen = max(maxLen, (int)word.size());
minLen = min(minLen, (int)word.size());
}
// 优化点2：wordDict 中字符串有最短长度限制，i 直接从 minLen 枚举
for (int i = minLen; i <= n; ++ i) {
// 枚举 s 的前 i 个字符，[0...i-1]
// 优化点1：考虑到 wordDict 中字符串有最长长度限制，i-j 不需要超过 maxLen
int start = max(i-maxLen, 0);
for (int j = start; j < i; ++ j) {
if (dp[j] && st.count(s.substr(j, i-j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}-
如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
# 如果是二维DP，内外的遍历顺序怎样都可以 # 对于一维DP，内层循环遍历容量需要倒序 for num in nums: for i in range(target, nums-1, -1):
-
如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
# 这里对于一维或者二维DP都可以，有时候二维DP还比较难比如 LC.377 # 如果涉及考虑排列组合问题需要注意遍历顺序 # 1. 组合问题（没有顺序）：先遍历物体，再遍历容量 # 2. 排列问题（有顺序）：先遍历容量，再遍历物体 for num in nums: for i in range(nums, target+1):