背包-01背包
题单介绍
### 背包问题模型
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci 得到的价值是 Wi。
求解将哪些物品装入背包可使价值总和最大。
#### 01背包
每种物品仅有一件，可以选择放或不放。
#### 状态表示
F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。
#### 状态转移方程
F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}
#### 初始化问题
- “恰好装满背包”：
F[0] = 0，
F[1..V ] 均设为 −∞
- 并没有要求必须把背包装满，而是只希望价格尽量大：
初始化时 F[0..V ]全部设为 0。
[01背包代码模板](https://www.luogu.com.cn/paste/i6367hpb)