01 背包

在约束下的优化问题：

$$\sum ^n{w}_i{x}_i\le C$$ $$x_i\in \{0,1\}$$

求

$$max\sum ^n{v}_i{x}_i$$

---

https://oi-wiki.org/dp/knapsack/#0-1-%E8%83%8C%E5%8C%85

状态为前 i 件物品和剩余的容量 w

状态对应价值函数 d 定义为目前状态背包内含有的价值

子结构为状态来自于选择第 i 件物品还是不选择第 i 件物品，即 $(i-1,w-w_i)$ 和 $(i-1,w)$

非常白痴的证明

状态转移方程为

$$d(i,w)=max\{d(i-1,w-w_i)+w_i,d(i-1,w)\}$$

通过 dp 算法复杂度为 $O(Cn)$

通过滚动数组压缩空间复杂度为 $O(C)$ ，具体操作是从后往前

---