acwing算法提高之动态规划--背包模型

1 基础知识

背包问题分类：

1. 01背包问题：N个物品有体积和价值属性，每个物品只有1个，背包容量V，求背包能装下的最大价值。
2. 完全背包问题：每个物品有无限个。
3. 多重背包问题：每个物品有$x_i$个。
   3.1 二进制优化。
   3.2 单调队列优化（即滑动窗口求最值）。
4. 分组背包问题：每组只能选择一类物品。
5. 混合背包问题。

上述问题是求最大价值，还有下列问题，

1. 求取最大价值时的具体方案。
2. 总价值为$W$时的方案数。
3. 二维费用的背包问题。
4. 有依赖的背包问题。

2 模板

暂无。。。

3 工程化