背包

01背包 完全背包: 滚动数组优化 01背包从前往后，完全背包从后往前

多重背包: 二进制优化 单调队列（滑动窗口）

完全背包对应前缀的最大值，而多重背包问题对应滑动窗口的最大值。 完全背包优化从后向前滚动，因为下一次需要用到上次的元素;

多重背包问题优化（单调队列） 多重背包问题不能用一维数组来优化。

01背包： 基本属性：花费（个体体积）与价值（容量）。 基本思路：枚举物品1 - n，每轮循环从读入物品属性，对于该物品枚举所有可能的体积。 优化方法：层优化，下一层用到上一层的数据，所以可以用滚动数组来压缩。 注意事项：1 注意从大到小枚举体积，因为下一层用到上一层j - v的数据，从小到大会覆盖掉。 2 注意从大到小枚举体积时体积的最小值不小于vi。

01背包的二维费用问题 基本属性中花费变为2项，基本思路不变. 状态表示：所有从前i个物品选，总费用1不超过v1,总费用2不超过v2的最大价值。 状态计算：在枚举每个物品对应的可能体积的时候体积需要考虑两项。 计算结果:f[MAX_NUM,V1.V2] 优化：与基本01中的一样，把第一维（物品）给优化掉。