背包模型

问题本质：多变量优化问题

给定n个物品，每个物品具有x个条件属性和y 个优化属性，要求选取一定数量的物品，满足：
1、对于每个条件属性，要求选取物品之和有最大值、最小值或者等于限定。
2、对于每个优化属性，给出最优值（最大或者最小），其中属性具有优先级顺序。
解题方法：动态规划
遍历每个物品数量，决定选还是不选
对于每个物品，依次对每个条件属性进行遍历
遍历该物品的选取个数（或者组内遍历），按照优先级顺序依次考察每个优化属性（实现从上一个物品数量到这个物品数量的动态转移）。

物品维度的写法差异

是否给物品添加一个维度的写法差异：本质是如何读取上一轮的数据问题。
- dp数组给物品数量添加一个维度，严格从上一次物品数量进行转移，可控制取物品的数量。
- dp数组无物品数量维度，条件属性的循环里，每次从后往前迭代，也实现从上一次物品数量进行转移，也可控制取物品数量。
- 对于完全背包问题，没有物品数量维度，条件属性的循环里，也可从前往后遍历。

问题分类1

根据每个物品可选数量，分为：
1、01背包：每个只能取一个。
2、完全背包：每个物品可以重复取。
3、多重背包：每个只有指定数量。
- 可直接做(有无物品维度都可)
- 可用二进制堆转化为01背包问题：将每个物品按照二进制堆拆分，转化为01背包问题 例题 。
- 单调队列优化：每加入一个物品时，对背包大小的遍历按照同余拆分成多轮遍历，每轮遍历中使用单调队列进行求解，区间大小是新加入物品的总体积，获取区间内的价值最大。例题
4、分组背包：每组只能选一个。把每组当成一个物品，动态转移进行最优选择的时候，进行组内搜索即可。（每天吃多少糖果、每个厂分多少机器这一类问题可以转化为分组背包问题）

问题分类2

1、条件属性限定最大值，优化属性求最小值（最常见）、方案案个数、具体方案。求方案个数时注意初始化，求具体方案时可以从最后一个物品往前求（涉及字典序时必须）。
2、条件属性限定等于某个值，没有优化属性，求方案个数、具体方案：如货币系统、组合数字。遍历方法同上，只是动态转移不是取最优，而是求和，注意初始化。例题
3、条件属性限定最小值，优化属性求最大值:例题
- dp数组初始化:dp[0][0] = 0,dp[i][j] = 无穷大
- 遍历方法同上，条件属性减去物品属性值可以为负数（因为是最小值限定），负数时取坐标0进行动态转移即可

其他变形

1、有依赖的背包问题：子节点选父节点必须选