~~众所周知，DP从入门到放弃。~~其实还是继续借用学姐的课件。因为蒟蒻的我啥也不会。

01背包：

有n件物品和一个容量为v的背包，每件物品有一件,第i件物品有体积w[i]和价值v[i]，把一些物品装进背包，求最大价值。
设f[i][j]表示前i件物品放进容量为j的背包可获得的最大价值
转移是：f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i]) （考虑第i个物品放还是不放）
优化空间 for (int i = 1; i <= n; i++)
for (int j = V; j >= max(V-sumw[n]-sumw[i - 1],w[i]); j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
用来更新f[j]的f[j - w[i]]还是f[i-1][j-w[i]]，所以这样是正确的 f[n][V]。
上面的滚动数组状态转移时，可简单看作j>=w[i]。

完全背包：

有n种物品和一个容量为v的背包，每种物品有无穷件,第i种物品有体积w[i]和价值v[i]，把一些物品装进背包，求最大价值。
设f[i][j]表示前i件物品放进容量为j的背包可获得的最大价值
转移是：f[i][j]=max(f[i−1][j],f[i−1][j−k * w[i]]+k * v[i]) 0~j/w[i]
（考虑第i个物品放几次）
优化 for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
用来更新f[j]的f[j - w[i]]可能是f[i][j-w[i]]，重复选了，所以这样是正确的。

多重背包：

有n种物品和一个容量为v的背包，每种物品有k[i]件,第i种物品有体积w[i]和价值v[i]，把一些物品装进背包，求最大价值。
设f[i][j]表示前i件物品放进容量为j的背包可获得的最大价值
转移是：f[i][j]=max(f[i−1][j],f[i−1][j−kw[i]]+kv[i]) （考虑第i个物品放几个）0<=k<=k[i]
优化：二进制拆分，把k[i]件物品，拆成log2(k[i])种物品，每种物品的体积是w[i]*2^k ，价值是v[i]*2^k

转化成01背包问题。

二维费用背包：

有n件物品、一个容量为v的背包和t元钱，每件物品有一件,第i件物品有体积w[i]、花费p[i]和价值v[i]，买一些物品装进背包，求最大价值。
设f[i][j][k]表示前i件物品放进容量为j的背包最多花k元前可获得的最大价值
转移是：for (int i = 1; i <= n; i++)
for (int j = V; j >= w[i]; j--)
for (int k = T; k >= p[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - w[i]][k - p[i]] + v[i]);

分组背包：

有n件物品和一个容量为v的背包，n件物品分成k组，同组不能同时放进背包,第i种物品有体积w[i]和价值v[i]，把一些物品装进背包，求最大价值。
设f[i][j]表示前i组物品放进容量为j的背包可获得的最大价值
转移是：
for (所有的组k)
for (int j = V; j >= 0; j--)
for (所有属于组k的i)
f[j] = max{f[j], f[j - w[i]] + v[i]}

树依赖背包：

n种物品，一个容量为V的背包，依赖关系成一棵树或森林，即父节点选了子节点才能选
设f[i][j]表示在以i为根的子树中用容量为j的背包，最大价值
k∈son[i]
for (int j = 0; j <= V; j ++) tmp[j] = 0;
for (int l = 0; l<= j; l++) tmp[j] = f[i][j - l] + f[k][l];
for (int j = 0; j <= V; j ++) f[i][j] = tmp[j];
for (int j = V; j >= w[i]; j--) f[i][j] = f[i][j - w[i]] + v[i];
for (int j = w[i] - 1; j >= 0; j--) f[i][j] = 0;
直接合并
O(NVV)

鸣谢

最后，我要对我的学姐lcr表示感谢，其实在此之前我根本不知道背包还可以分这么多种。