背包DP
最为基础的DP
突然发现自己dp极其菜，背包一个不会/kk(我没开玩笑)
那全部学一遍。
01背包
问题:n 种物品，每种物品有一个大小 $v_i$，一个价值 $c_i$ 可以选择一个或不选，求背包容量为 m 的情况下(指所选物品大小之和小于等于m)选择的物品价值和的最大值。
我们可以设 $f_{i,j}$ 表示在前 $i$ 个物品中选择，背包容量为 $j$ 时可以取到的价值和最大值。
考虑选择一个物品带来的影响：会占用 $v_i$ 的容量，并且获得 $c_i$ 的价值。不选即无变化。不难推出转移方程。
\[f_{i,j}=max\{f_{i-1,j},f_{i-1,j-v_{i}}+c_{i}\}\]发现 $f_{i,j}$ 只会受 $f_{i-1,x}$ 的影响，所以考虑省去一维。
\[f_{j}=max\{f_{j},f_{j-v_{i}}+c_{i}\}\]代码实现：
for(int i=1;i<=n;++i){
for(int j=m;j>=v[i];--j){
f[j]=Max(f[j],f[j-v[i]]+c[i]);
}
}
Q1：为什么第二层循环需要倒着枚举。
A1：这样的目的其实是为了保证每个物品最多被选一次。如果正着枚举，会发现 $f_j$ 会影响到 $f_{j+v_i}$ 进而又影响到 $f_{i+2\times v_i}$，这样会使物品能被选无数次。
Q2：没选满容量的情况为最优解，但回答的答案是 $f_m$，这样不会错吗？
A2：答案是不会，因为我们在枚举的时候是对于每个可行容量枚举的，也就是说有就算啥也没选也算作占据一定容量，就可以解决问题。
完全背包
问题：有 n 种物品，每个物品有大小 $v_i$ 和 价值 $c_i$，每种物品可以选择无数次，求在背包容量为 m 时的所选物品价值和最大。
在01背包Q1中已经提到了，就不多复述了。
代码实现：
for(int i=1;i<=n;++i){
for(int j=v[i];j<=m;++j){
f[j]=Max(f[j],f[j-v[i]]+c[i]);
}
}
多重背包
问题:n 种物品，每种物品有一个大小 $v_i$，一个价值 $c_i$ 最多可以选择 $t_i$ 个，求背包容量为 m 的情况下(指所选物品大小之和小于等于m)选择的物品价值和的最大值。
本质是01背包，只是添加了选择个数的条件，多添加一层循环 k 表示选择的次数即可。转移方程如下：
\[f_j=max\{f_j,f_{j-k\times v_i}+k\times c_i\}\]代码实现：
for(int i=1;i<=n;++i){
for(int j=m;j>=v[i];--j){
for(int k=0;k<=t[i]&&k*v[i]<=j;++k){
f[j]=Max(f[j],f[j-k*v[i]]+k*c[i]);
}
}
}
优化：
混合背包
问题:n 种物品，每种物品有一个大小 $v_i$，一个价值 $c_i$ 有的可以选择 $t_i$ 个，有的只能最多选一个，有的可以选无数个，求背包容量为 m 的情况下(指所选物品大小之和小于等于m)选择的物品价值和的最大值。
上面三种结合枚举物品时判断是什么类型的背包即可，就不多说了。
多维背包
与其他背包区别在于有多个容量，只需要对于每个容量背包一次即可。（具体是什么背包看题意）
分组背包
每组物品中只能选一个出来。
对于每一组跑01背包即可。
代码实现：
for(int k=1;k<=T;++k)
{
for(int j=m;j>=0;--j)
{
for(int i=1;i<=pos[k][0];++i)
{
int p=pos[k][i];
if(j>=w[p]) dp[j]=max(dp[j],dp[j-w[p]]+v[p]);
}
}
}