零、一些记号与约定
物品种类个数：\(n\)。
背包最大容量：\(m\)，无特殊声明外非负。
每种物品的体积：\(v_i\)，无特殊声明外非负。
每种物品的价值：\(w_i\)。
每种物品的数量：\(c_i\)，无特殊声明外 \(c_i=1\)。
物品体积的最大值：\(V=\max_{i}{v_i}\)。
物品价值的最大值：\(W=\max_{i}{w_i}\)。
物品数量的最大值：\(C=\max_{i}{c_i}\)。
一、朴素动态规划
01 背包
\(n\) 个物品，每个物品有体积 \(v_i\) 和价值 \(w_i\)，求体积和不超过 \(m\) 的情况下价值和的最大值。
设 \(f_{i,j}\) 表示当前考虑了前 \(i\) 个物品，体积和为 \(j\) 的最大价值和。
转移即为 \(f_{i-1,j}+w_i \rightarrow f_{i,j+v_i}\)。
考虑把第一维去掉，设 \(f_j\) 表示目前体积和为 \(j\) 的最大价值和。
每次新加第 \(i\) 个物品，有转移 \(f_j+w_i \rightarrow f'_{j+v_i}\)。实际上不需要 \(f'\)，因为 \(v_i \geq 0\)，所以可以直接倒序枚举 \(j\) 转移来避免后效性。
时间复杂度 \(\mathcal O(nm)\)，空间复杂度 \(\mathcal O(n+m)\)。
for(int i=1;i<=n;i++) for(int j=m-v[i];j>=0;j--) f[j+v[i]]=max(f[j+v[i]],f[j]+w[i]);
完全背包
\(n\) 个物品，每个物品有体积 \(v_i\) 和价值 \(w_i\)，数量有无限个（\(c_i=+\infty\)），求体积和不超过 \(m\) 的情况下价值和的最大值。
跟 \(01\) 背包差不多，只不过转移变为 \(f_j+kw_i \rightarrow f'_{j+kv_i}(k \geq 1)\)，直接顺序 dp 即可。
时间复杂度 \(\mathcal O(nm)\)，空间复杂度 \(\mathcal O(n+m)\)。
for(int i=1;i<=n;i++) for(int j=0;j<=m-v[i];j--) f[j+v[i]]=max(f[j+v[i]],f[j]+w[i]);
多重背包
\(n\) 个物品，每个物品有体积 \(v_i\) 和价值 \(w_i\)，数量有为 \(c_i\)，求体积和不超过 \(m\) 的情况下价值和的最大值。
还是考虑 01 背包的 dp 形式，转移变为 \(f_j+kw_i \rightarrow f'_{j+kv_i}(k \in [1,c_i])\)。
二进制分组优化背包
将每个 \(c_i\) 拆成 \(2^0+2^1+\cdots+2^k+(m-2^{k+1}+1),m-2^{k+1}+1 \in [0,2^{k+1})\)，容易证明 \([0,c_i]\) 的所有数都可以被这 \(\log{c_i}+1\) 个数表示出来。
注意不是将 \(c_i\) 直接二进制拆分！！！
那么这就变成了 \(n\log C\) 个物品的 01 背包问题。举个例子，第 \(i\) 个物品的 \(c_i\) 被分成的其中一个数为 \(x\)，那么这个新物品的体积为 \(xv_i\)，价值为 \(xw_i\)，数量为 \(1\)。
时间复杂度 \(\mathcal O(nm\log C)\)，空间复杂度 \(\mathcal O(n\log C+m)\)。
单调队列优化背包
每次新加第 \(i\) 个物品，将 \(f_j\) 按照 \(j \bmod v_i\) 分组，那么显然只有同一组的会互相转移。
假设 \(j_1,j_2\) 属于同一组且 \(j_1<j_2\)，那么转移可以改写为 \(f_{j_1}+(\lfloor \frac{j_2}{v_i} \rfloor-\lfloor \frac{j_1}{v_i} \rfloor)w_i \rightarrow f'_{j_2}\)，且要求 \(\lfloor \frac{j_2}{v_i} \rfloor-\lfloor \frac{j_1}{v_i} \rfloor \leq c_i\)。
直接用单调队列优化，时间复杂度 \(\mathcal O(nm)\)，空间复杂度 \(\mathcal O(n+m)\)。