动态规划（一）：组合型DP之背包问题二

优化一维空间：01背包倒序，完全背包正序

1.AcWing 1024.装箱问题

01背包求最大价值（体积：至多为j）

1.01背包求最大价值的变种：体积==价值

点击查看代码

2.AcWing 278.数字组合

01背包求恰好体积的方案数（体积：恰好j）

1.求方案数注意初始化

点击查看代码

3.AcWing 1021.货币系统

完全背包求恰好体积的方案数（体积：恰好为j）

1.求方案数注意初始化

点击查看代码

4.AcWing 1019.庆功会

朴素版多重背包求最大价值（体积：至多为j）

1.无

点击查看代码

5.AcWing 1022.宠物小精灵之收服

二维01背包求最大价值（体积：至多为j）

1.二维背包问题（两个条件限制）
2.最大价值的情况下最多能剩余的体积

点击查看代码

6.AcWing 1020.潜水员

二维01背包求最小价值（体积：至少为j）

1.注意求最小价值时的初值设定，不可能事件要设为正无穷（反之求最大值时，不可能事件应设为负无穷）
2.注意体积是至少为j，所以f[i][j-v1[i]][k-v2[i]]中，j-v1[i]或者k-v2[i]为负数时是有实际意义的！！！

点击查看代码

7.AcWing 11.背包问题求方案数

01背包求最大价值的方案数（体积：至多为j）

法一：求g[i][j]：前i个物品，体积不超过j的情况下最大价值的方案数
    f[i][j]：前i个物品，体积不超过j的情况下最大价值
法二：求g[i][j]：前i个物品，体积恰好为j的情况下最大价值的方案数
    f[i][j]：前i个物品，体积恰好为j的情况下最大价值
    注意求最大价值时，不可能事件初始化为负无穷！！！

点击查看代码

8.AcWing 12.背包问题求具体方案

01背包求最大价值的具体方案（体积：至多为j）

1.倒序枚举01背包：倒序枚举（倒序正序结果一样，但过程值不一样）
f[i][j]：考虑第i个到最后一个的物品中选择，体积不超过j的最大价值
2.求最小字典序，顺序枚举贪心，能选就选

点击查看代码