艋佰傧 发表于 2025-7-15 16:27:27

BITACM 2025 暑期集训 B组 笔记

Notes

DP基础

0/1背包

有\(n\in\N\)个物品，重量分别为\(\vec w\in(\N^*)^n\)，价值分别为\(\vec v\in(\N^*)^n\)。背包容量为\(c\)，求包里能装下物品的最大价值。
设\(f_{i,j}\)表示对于前\(i\)个物品，容量为\(j\)的背包能装下物品的最大价值。
递推边界：

\
状态转移方程：

\[f_{i+1,j}=\left\{\begin{align}&0&&(j
页: [1]
查看完整版本: BITACM 2025 暑期集训 B组 笔记