前言
明天是咱们解说 动静布局专题 中的「背包问题」的第十一篇。
明天将会学习「混合背包」问题，同时也是咱们「背包问题」的第一阶段的最初一节。
明天首先会和大家回顾之前学过的三种背包问题。
而后通过一道「混合背包」问题，来将咱们之前学的几种背包问题串联起来。
心愿通过本篇内容，大家会对背包问题有更清晰的意识。
另外，我在文章结尾处列举了我所整顿的对于背包问题的相干题目。
背包问题我会依照编排好的程序进行解说（每隔几天更新一篇，确保大家消化）。
你也先能够尝试做做，也欢送你向我留言补充，你感觉与背包相干的 DP 类型题目 ~
回顾三种传统背包问题
后面咱们曾经学完了三种传统背包问题了。
这里再回顾一下三种传统背包：
- 01 背包：强调每件物品「只能抉择一次」。对其进行「一维空间优化」并不能升高工夫复杂度，进行「一维空间优化」时要求「容量维度“从大到小”进行遍历」。
- 齐全背包：强调每件物品「能够抉择有限次」。对其进行「一维空间优化」具备数学意义，能够将工夫复杂度从 升高到，进行「一维空间优化」时要求「容量维度“从小到大”进行遍历」。
- 多重背包：强调每件物品「只能抉择无限次」。对其无论是进行「一维空间优化」还是「一般扁平化」都不能升高工夫复杂度，要利用额定的优化伎俩：二进制优化 或 枯燥队列优化。
三种背包问题的 「难易水平」 是「递增」，但 「重要水平」 则是「递加」 的。
尽管「多重背包」的 二进制优化 和 枯燥队列优化 都比拟 trick。
但其实「多重背包」并没有这么常见，以至于在 LeetCode 上我都没找到与「多重背包」相干的题目。
同时三种背包问题都有 「不超过」 和「恰好」两种状态定义。
这两种状态定义只在「初始化」上有区别。
至于该如何初始化则要抓住 什么样的状态是非法的：
-
对于「不超过」的状态定义：均为非法值。
代表不思考任何物品，背包容量「不超过」的所获得的最大价值为。
-
对于「恰好」的状态定义：中只有 为非法值，其余值均为“有效值”。
代表不思考任何物品，只有背包容量「恰好为」时所获得的最大价值为；其余容量「恰好为非」是无奈获得无效价值的（因为不思考任何物品）。
总的来说，三种背包问题都很经典（实质上都是组合优化问题），以至于「背包问题」间接成为了一类的动静布局模型。
我的倡议是三种背包都须要把握。但如果切实要分侧重点的话，我更违心你将大多数工夫花在「01 背包」和「齐全背包」上。
混合背包
给定物品数量 和背包容量。第 件物品的体积是，价值是，可用数量为：
- 当 为 代表是该物品只能用一次
- 当 为 代表该物品能够应用有限次
- 当 为任意正整数则代表可用 次
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
根本剖析
混合背包其实就是综合了「01 背包」、「齐全背包」和「多重背包」三种传统背包问题。
咱们晓得在一维空间优化形式中「01 背包」将以后容量 依照“从大到小”进行遍历，而「齐全背包」则是将以后容量 依照“从小到大”进行遍历。
同时「多重背包」能够通过「二进制优化」彻底转移成「01 背包」。
所以咱们只须要依据第 个物品是「01 背包」物品还是「齐全背包」物品，抉择不同的遍历程序即可。
代码：
class Solution {public int maxValue(int N, int C, int[] w, int[] v, int[] s) {
// 结构出物品的「价值」和「体积」列表
List<Integer> worth = new ArrayList<>();
List<Integer> volume = new ArrayList<>();
for (int i = 0; i < N; i++) {int type = s[i];
// 多重背包：利用「二进制优化」转换为 0-1 背包问题
if (type > 0) {for (int k = 1; k <= type; k *= 2) {
type -= k;
worth.add(w[i] * k);
volume.add(v[i] * k);
}
if (type > 0) {worth.add(w[i] * type);
volume.add(v[i] * type);
}
// 01 背包：间接增加
} else if (type == -1) {worth.add(w[i]);
volume.add(v[i]);
// 齐全背包：对 worth 做翻转进行标记
} else {worth.add(-w[i]);
volume.add(v[i]);
}
}
// 应用「一维空间优化」形式求解三种背包问题
int[] dp = new int[C + 1];
for (int i = 0; i < worth.size(); i++) {int wor = worth.get(i);
int vol = volume.get(i);
// 齐全背包：容量「从小到大」进行遍历
if (wor < 0) {for (int j = vol; j <= C; j++) {
// 同时记得将 worth 从新翻转为正整数
dp[j] = Math.max(dp[j], dp[j - vol] - wor);
}
// 01 背包：包含「本来的 01 背包」和「通过二进制优化的齐全背包」// 容量「从大到小」进行遍历
} else {for (int j = C; j >= vol; j--) {dp[j] = Math.max(dp[j], dp[j - vol] + wor);
}
}
}
return dp[C];
}
}
就这样咱们解决了这个混合背包问题。
先将一个「多重背包」问题通过「二进制优化」的思路，转化为「01 背包」问题。
而后依据物品是属于「01 背包」还是「齐全背包」决定容量 是 ” 从大到小 ” 还是 ” 从小到大 ” 进行推算。
换句话说就是依据物品的类型不同，抉择不同的转移形式。
总结
明天咱们在学习「混合背包」之前先梳理了后面学的三种传统背包问题。
三种传统背包的次要区别在于「物品可被抉择的次数」，其中「01 背包」的一维空间的优化形式是其余背包问题的根底。
对于「齐全背包」和「多重背包」而言，一个能够抉择「任意个数的物品」，另外一个则存在「抉择物品的上界」。
这导致这两种背包问题在转移某个 时，其实实质是别离在求「整个前缀的最值」和「滑动窗口的最值」。
这就意味着「齐全背包」能够间接通过一维空间优化升高工夫复杂度；而「多重背包」则要通过「二进制优化」（缩小总的物品数量）或者「枯燥队列优化」（实现间接求得滑动窗口最值）来升高工夫复杂度。
最初
到这一节完结，咱们就曾经实现「背包问题」的第一阶段的学习了 🎉 🎉
接下来的「背包问题」更多的偏差于「多维」、「分组」、「有依赖」、「求计划数 / 具体计划」此类问题。
这类问题往往才是真正用来考查「背包思维」的题目，第一阶段的学习更多的是模板题，打基础用的。
持续加油吧 ~
另外，最近一段时间的公众号的更新频率的确降落了
不少同学通过各种渠道（LeetCode 评论区、知乎、公众号后盾）催更 …
然而我真的没有偷懒啦 🤣
这就来跟大家分享最近在忙些什么：
- 首先必定是忙工作啦
- 而后是正在将内容整顿成排版和程序都比拟正当的 pdf，前面会公开出来给大家下载
- 最初一个则是彩蛋预报：最近在和 LeetCode 策动单干出两本 LeetBook 🎉 🎉 目前曾经靠近序幕，到时依然会以「收费 & 非会员」的模式提供给大家 🤣 这样大家就能取得更好的学习体验啦 ~
敬请期待叭 ~
过了这一阵子后，公众号会复原到「一周 3~4 篇」的更新频率滴 ~
背包问题（目录）
因为「背包问题」很多模板题在 LeetCode 上都没有模板题，同时公众号不能放外链，所以今晚建了一个背包仓库。
前面会给每篇文章配相应的原题地址，欢送 mark ~
（继续更新）残缺地址：https://github.com/SharingSou…
- 01 背包 : 背包问题 第一讲
- 【练习】01 背包 : 背包问题 第二讲
- 【学习 & 练习】01 背包 : 背包问题 第三讲
- 齐全背包 : 背包问题 第四讲
- 【练习】齐全背包 : 背包问题 第五讲
- 【练习】齐全背包 : 背包问题 第六讲
- 【练习】齐全背包 : 背包问题 第七讲
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【上】多重背包（优化篇）: 背包问题 第九讲
- 【下】多重背包（优化篇）: 背包问题 第十讲
- 混合背包 : 本篇
- 【练习】混合背包
- 分组背包
- 【练习】分组背包
- 多维背包
- 【练习】多维背包
- 树形背包
- 【练习篇】树形背包
- 背包求计划数
- 【练习】背包求计划数
- 背包求具体计划
- 【练习】背包求具体计划
- 泛化背包
- 【练习】泛化背包