背包模型 ————— 本质上是有限制的选择问题

遇到DP问题 先确定是什么模型
确实是背包模型后
再去思考什么是物品什么是体积

背包问题就是就是一个物品有两重属性

01背包

01背包问题就是一个物品只有选择和不选择两种情况的并且总的情况另外一个属性有一定的条件 有限制的选择问题

01背包使用的技巧 用滚动数组优化
如果一个状态只用到了上一个状态的话 即i层只用了i - 1层的状态 就可以优化掉一维的空间
01背包的题眼 1.一个物品只有选择和不选择的两种情况
             2.题目种出现的状态可以抽象为 物品数量 和 背包体积

常见的几种01背包题型 
   1.**01背包记录路径** P2196 [NOIP1996 提高组] 挖地雷
   2.**01背包求方案数** Acwing 278 数字组合 直接初始化边界情况（递推的初始条件） 然后将转移方程改为加法
   3.**二维01背包问题** Acwing 1022 小精灵收复
   4.**二维01背包至少问题** Acwing 1020 潜水员 ———— 枚举的范围和绝对值
   5.**二维背包求方案数** Acwing 11 这是一个最优性求方案书，可以创建两个数组分别表示 方案数 和 体积数
   6.**背包问题求具体的方案**  Acwing 12 ~~本质上背包问题输出具体方案 其实就是判断出每个物品是否被选~~

完全背包

完全背包就是 总的情况在满足另外一个属性满足的情况下，一个物品可以无限使用

完全背包的题眼 ———— 一个物品可以使用无数次
完全背包枚举的时候有一维需要按照从小到大来枚举
常见的完全背包题型
1.完全背包求方案数 Acwing 1023 买书 Acwing 货币系统
2.完全背包 ———— 状态为至少类型 P2918 [USACO08NOV]Buying Hay S
3.完全背包应用体积变化 ———— 洛谷P1853 投资的最大效益 这题是一个完全背包的模型 但注意的是需要注意抽象出来的体积是变化的

多重背包

二进制打包枚举 单调队列优化
多重背包就是物品数量有了限制
注意枚举的时候 应该先枚举体积在枚举物品的数量
如果先枚举数量的话，那么转移方程的含义就会变

  常见的几种多重背包题型
  1.**多重背包求方案数** Acwing 451 摆花

  以下是二进制优化枚举多重背包的代码 ———— 细细品尝
  cin >> v >> w >> s;
        for(int k = 1;k <= s;k *= 2){
            for(int j = V;j >= k * v;j --)
             dp[j] = max(dp[j],dp[j - k * v] + k * w);
            s -= k; 
        }
        if(s){
            for(int j = V;j >= s * v;j --)
              dp[j] = max(dp[j],dp[j - s * v] + s * w);
        }

分组背包

 ~~分组背包的难点就在于如何能看出这是分组背包~~
   先循环体积再循环决策
   常见的分组背包题型
   1.**分组背包求方案路径**  Acwing 1013 机器分配 注意这个不能简写为1维度，写一个路径数组来储存一个点是哪个点转移过来的
   2.**分组背包 二进制枚举 ** Acwing 487 金明的预算方案