概念
0-1 背包
有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
我们设 \(dp_i,_j\) 表示选了前 \(i\) 个，重量为 \(j\) 的最大价值。
显然可以选或不选，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
完全背包
有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大，每个可以选多次。
显然，可以在 \(DP\) 转移的时候变一下，dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]]);
多重背包
有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，价值是 \(D_i\)，可以选 \(L_i\) 个。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
\(DP\) 时可以枚举选了几个。
二进制优化
把物品拆成 \(\log n\) 个数量，这样可以优化到 \(\log n\)。
空间优化
- 滚动数组
- 重复利用
因为 dp[i][j] 只会转移到 dp[i + 1][j] 和 dp[i + 1][j + v[i + 1]]，所以可以重复利用数组。
注意循环方向。
树上背包
首先这里很容易写错。
不能直接枚举，要记录一个字树，然后枚举时取最小值。
这样复杂度就降下来了。
恰好的背包
初始化一个值即可。
时间复杂度
0-1 背包：\(O(nm)\)。
完全背包：\(O(nm)\)。
多重背包（暴力）：\(O(nml)\)。
多重背包（二进制优化）：\(O(nm\log l)\)。
多重背包（单调队列优化）：\(O(nm)\)。
树上背包（暴力）：\(O(n^2m)\)。
树上背包（优化）：\(O(nm)\)。
例题
F
注意到，每增加一次，\(t_i\) 就增加 \(1\)。
我们就会发现，要求的就是 \(t\) 的总和的容量大于或等于 \(n\) 的背包。
I
先按 \(d\) 排序。
然后就是一个背包，然后输出路径。