01背包分析

每个物品只有一件
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w)

完全背包：

每个物品有无穷多件
f[i][j] = max(f[i-1][j], f[i][j-v]+w)

多重背包问题

每个物品最多有各自指定件数
f[i][j] = max(f[i-1][j], f[i-1][j-k*v]+k*w)

PS:为什么不能用完全背包的优化思路 而是根据01背包思路做修改加上3重循环

因为 多重背包 转移方程并不与完全背包相同
假设第 i 种物品只有 2 个, 且 j >= 3v 且 j<4v, 转移方程如下：
完全背包会用尽背包空间
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+w, f[i-1][j-3v]+w)
f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w, f[i-1][j-3v]+w)
而多重背包不一定会用尽空间
f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+w)
f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w, f[i-1][j-3v]+2w)
f[i][j-v] 公式的还多了f[i-1][j-3v]+w项不能转移

如果用了完全背包的优化思路, 转移方程就成了
f[i][j] = max(f[i-1][j], f[i][j-v]+w) = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w)

分组背包

物品有多组,每组 s件物品，每组只能选一件
f[i][j] = max(f[i-1][j], f[i-1][j-v[0]]+w[0], f[i-1][j-v[1]]+w[1],..., f[i-1][j-v[1]]+w[1])