0-1背包问题

• 问题：$n$ 个物品，重量 $w_i$，价值 $v_i$，背包容量 $C$。每个物品只能选0个或1个。
• 状态定义：$m[i][j]$ 表示可选物品为前 $i$ 个，背包容量为 $j$ 时的最大价值。
• 转移方程： $m[i][j]=\{\begin{array}{ll}m[i-1][j]& j<w_i\text{ (装不下)}\\ \max \{m[i-1][j],m[i-1][j-w_i]+v_i\}& j\ge w_i\text{ (能装下，选或不选)}\end{array}$
• 复杂度：$O(nC)$。
• 对比：如果物品可以分割（分数背包），则应使用贪心算法。