笔记汇总

很久以前，人们就发现了 $DFS$ 会多次 重复选择计算同一个数 的情况。

为了解决这类冗余浪费，人们决定用 值域映射 的方式，以空间换时间。

而不是完整的枚举完理论的 $2^n$ 选法，对于已经找到局部最优解的值域，可以直接返回

这个算法就叫作 背包：

背包利用的就是 值域很小 这一特点来重叠 子结构，贡献一致即可。

所以背包本质上处理的应该是一个集合中的所有物品，选或不选对应权值的变化。

有时候这样的权值甚至是 多维度的，我们进行的就是多个维度上的重叠子结构。

可能是负数，可能操作不是加减，适用于任意复杂的操作，但是关键在于状态转移的 单调性，否则没法进行状态转移（对于特殊情况比如异或，我们就不需要用背包处理了）