背包 DP 专项 知识梳理
【信奥题单】DP 之 背包 DP 专项
0x00 前言
背包 DP 与普通 DP 类似，也需满足普通 DP 的几个条件，找到 \(dp\) 数组定义、初始化、循环顺序、状态转移方程、题目所求。其变化众多，考验思维分析。
0x01 题型特点
对于背包 DP 的题目，一般都是选出一些物品，且给定代价、价值、限制、背包类型，让我们求极值、方案数、抑或是可行性。对于代价、价值、限制，题目中不一定会明显给出，需要我们自己根据题目要求寻找，而背包类型则较为好分辨，只需了解题目选择物品的逻辑即可。
0x02 模板代码
背包问题经典的五类基本题型。
一、0-1 背包
对于每个物品只能取一次的背包问题，被称为 0-1 背包。解析详见这篇文章。
二、完全背包
对于每个物品无限次的背包问题，称为完全背包。解析详见这篇文章。
三、分组背包
对于将物品分为多个组，每组只能取一样物品的的背包称为分组背包，解析详见这篇文章。
四、多重背包
对于一个物品可以取有限次（不一定为 \(1\)） 的背包称为多重背包，解析详见这篇文章，有时需要二进制优化，另外还有单调队列优化，在 S 组 DP 中会有。
五、混合背包
一堆物品有些是 0-1 背包，有些是完全背包，有些是多重背包，即将 0-1 背包、完全背包、多重背包混合起来的背包就是混合背包，详见这篇文章。
0x03 经典题型
在一个基本模板上可以叠加多种题型，使题目千变万化。
一、方案数
对于方案数的背包，只需对当前元素加上转移过来的方法即可，详见这篇题解。
二、可行性
判断对于给定限制是否可行，详见这篇题解。
对于有些题目，可能需要反转题目给定的代价和价值，用可行性背包加上枚举答案求最值，如这篇题解。
三、多维背包
对于一个物品有多个代价的背包为多维背包，解题时只需多开一维数组，多套一层循环即可，详见这篇题解。
四、多代价
对于有多个代价的背包，可以给每个背包开一个数组，分别按题目要求处理。也可以采用次要性动态规划，详见这篇题解。
五、负代价
对于一些代价和为负的背包，可以通过同加一个大数让下标变为正，既不改变相对位置，又符合规定，详见这篇题解。
六、余数
对于要求代价和为某一定值 \(m\) 的倍数，可以重新以代价模 \(m\) 的余数为数组下标进行状态转移，详见这篇题解。