背包九讲笔记

初始化问题

 当所求为恰好填满背包时；初始化状态除了j=0以外的值都为inf；原因在；此时的f_i,j表示的是恰好填满背包的最大值；而初始除了j=0以外的背包都没有填满；故其他状态赋值inf.

而所求最大能填多少时，初始状态都赋值为0(原因同理).

①01背包

空间优化：因为每次fi,j的状态都由与f_i-1有关的项表示所以可以优化到一位数组上求解此问题，

而此时需要注意的是j应该倒着枚举；因为正着枚举的前项改变变成了实际上的fi,j而我们想要的是f_i-1,j，即正向枚举会影响状态转移.

普通01背包做法 需要注意0~c[i]时的状态转移即为f_i,j=f_i-1,j不然会寄.

②完全背包

铸币思路：直接01背包的处理方式，对每一件物品，设其有能把背包填满项，vector维护一下，直接当成01背包做.

优化：由于一件物品可以无限次的选，那么可以考虑转移方程为：f_i,j=max(f_i-1,j,f_i,j-c[i]+w[i])故考虑01背包时我们的优化处理，即我们通过逆序枚举来使得转移方程的右项为此轮枚举i未改变的值；那么我 们只要顺序枚举就能让右项变成此轮枚举过的i

③多重背包

二进制优化：将每件物品的个数pi表示成二进制可得其最高位的数；那么可以将其进行拆分为 1,2,4,8,...,2^k-1,p-2^k+1.

可以发现通过上面的拆分的任意组合，可以且仅可以拼凑出0-p之间的任意自然数.而后即可转换为01背包处理.复杂度为O(V∑logp_i)

优先队列优化：

前置知识：单调队列 参考题目：滑动窗口

blog.csdn.net/flyinghearts/article/details/5898183太懒了看巨巨写的吧

代码可以参考洛谷题目 宝物筛选 的题解

④混合背包

⑤分组背包

⑥二维费用背包

⑦有依赖的背包

其实都是上述三种分析问题的变式应用，理解前三种也就没啥好说的了...

⑧泛化物品

没看懂，有题目看懂了更