BITACM 2025 暑期集训 B组 笔记

Notes

[2025-07-15] DP基础

0/1背包

有\(n\in\N\)个物品，重量分别为\(\vec w\in(\N^*)^n\)，价值分别为\(\vec v\in(\N^*)^n\)。背包容量为\(c\)，求包里能装下物品的最大价值。

设\(f_{i,j}\)表示对于前\(i\)个物品，容量为\(j\)的背包能装下物品的最大价值。
递推边界：

\[f_{0,i}=0\ (i\in\N,\ i\leq c)\]
状态转移方程：

\[f_{i+1,j}=\left\{\begin{align}&0&&(j