本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-22 14:31:18
01背包
由于01背包太过经典，所以一定要把每一个细节理解透彻！
有 $n$ 个物品和一个容量为 $m$ 的背包，每个物品有体积 $w_i$ 和价值 $v_i$，求用这个背包所能装下的最大价值。
设 $f_{i,j}$ 表示只考虑前 $i$ 个物品，体积不超过 $j$ 的最大价值。如果我们算完了前 $i-1$ 个物品的所有结果，那么第 $i$ 个物品有选和不选两种情况。如果不选，则结果为 $f_{i-1,j}$；如果买，则：由于选了 $i$ 后体积不超过 $j$，那么选 $i$ 之前体积就不能超过 $j-w_i$，而选了 $i$ 之后获得的价值就多了 $v_i$，所以结果为 $f_{i-1,j-w_i}+v_i$。这样，我们就得出了经典的状态转移方程：$f_{i,j}=max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$。
接下来，我们再考虑一些细节。对于 $f$ 数组的初始化，我们可以将所有的方案全部赋值为 $0$，因为无论考虑多少物品，无论体积不超过多少，都一定有一种符合要求的方案：一个也不选。这时的价值就是 $0$。
然后就到了经典的空间优化：我们可以发现 $f_i$ 这一行只与 $f_{i-1}$ 这一行有关，所以我们可以将 $i$ 这一维省略。这样，当我们准备求 $f_j$ 时，我们要求 $f_j$ 和 $f_{j-w_i}$ 都还没有被更新过。因为我们正准备更新 $f_j$，所以第一个要求可以保证，那么怎么保证 $f_{j-w_i}$ 没有被更新过呢？答案就是倒序更新（这样就在更新 $f_j$ 之后才会更新到 $f_{j-w_i}$ 了）。
接下来还有一个经典的常数优化：因为当 $j<w_i$ 时，转移方程中 $f_{j-w_i}$ 不存在，不需要考虑更新，所以 $j$ 必须大于等于 $w_i$，也就是倒序枚举时 $j$ 只需要从 $m$ 枚举到 $w_i$。
所以，我们就得到了经典的01背包代码：
for(int i=1;i<=n;i++)
for(int j=m;j>=w_i;j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[m]<<endl;
例题：采药
正好填满的01背包
是一个01背包经典的变形，题意基本与01背包相同，但要求背包必须填满。
这时，$f$ 数组的意义发生了一点变化：$f_{i,j}$ 表示只考虑前 $i$ 个物品，体积恰好为 $j$ 的最大价值。
但是，仔细推理一下，就会发现，状态转移方程和01背包一模一样，空间优化和常数优化也都通用。那不一样的地方在哪里呢？答案是初始化。由于要求体积恰好为 $j$，所以当 $j\ne 0$ 时，不允许一个也不选，所以初始化为负无穷（表示目前没有任何方案满足条件），当 $j=0$ 时，才存在一个也不选的方案，这时才能初始化为 $0$。
代码：
memset(f,-0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[m]<<endl;
二维费用背包
有两维费用（如：一个事件既要消耗时间也要消耗金钱，获得一定价值）的01背包。
将01背包多开两维费用，其他完全相同。
代码：
\/\/背包第一维容量为m，背包第二维容量为t
for(int i=1;i<=n;i++)
for(int j=m;j>=w1[i];j--)
for(int k=t;k>=w2[i];k--)
f[j][k]=max(f[j][k],f[j-w1[i]][k-w2[i]]+v[i]);
cout<<f[m][t]<<endl;
例题：榨取kkksc03
完全背包
又是一个经典模型，也必须要理解透彻。题意与01背包基本相同，但每个物品能选无数遍。
同样设 $f_{i,j}$ 表示只考虑前 $i$ 种物品，体积不超过 $j$ 的最大价值。这时如何更新呢？如果我们不选这个物品，那么结果为 $f_{i-1,j}$；如果选，那么结果为 $f_{i,j-w_i}+v_i$。这是为什么呢？在01背包中，我们当前要选 $i$，那么选这个 $i$ 之前，只能考虑前 $i-1$ 个物品，所以要从 $f_{i-1,j-w_i}$ 转移，但是在完全背包中，每个物品可以选无数次，所以选这个 $i$ 之前，$i$ 也是可以选的，所以要从 $f_{i,j-w_i}$ 转移而来。这样，我们就得到了最终的转移方程：$f_{i,j}=max(f_{i-1,j},f_{i,j-w_i}+v_i)$。
同01背包一样，我们也可以省略掉 $i$ 这一维。这时，当我们求 $f_j$ 时，要求变成 $f_j$ 还没有更新，而 $f_{j-w_i}$ 已经更新过了（因为我们要用的是 $f_{i,j-w_i}$ 而不是 $f_{i-1,j-w_i}$）。同样，第一个要求能直接满足，对于第二个要求，我们只需要正序枚举 $j$ 即可。所以，最终转移方程与01背包一样，但 $j$ 的枚举顺序变成了正序。
代码：
for(int i=1;i<=n;i++)
for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[m]<<endl;
例题：疯狂的采药
多重背包
题意与01背包基本相同，但每种物品能选 $x_i$ 次。
一个很容易想到的思路为将一种物品选 $x$ 次转换成 $x$ 个完全相同的物品，再做01背包。
这样的复杂度显然不够优秀，所以我们考虑优化。我们希望将每个物品选 $x$ 次转换成若干个物品，使得无论想选多少次都能用这若干个物品凑出来。一个较为明显的做法就是二进制分解。例如，我们有一个物品能选20次，我们就将它分解成一个 $1$ 倍物品、一个 $2$ 倍物品、一个 $4$ 倍物品、一个 $8$ 倍物品和一个 $5$ 倍物品（几倍物品指的是体积和价值都为原物品的几倍）。易证，这一定满足我们的条件。这样，我们就将一个物品选 $x$ 次分解成了 $\log(x)$ 个物品，然后再跑一遍01背包即可。
代码：
for(int i=1;i<=n;i++)
for(int tmp=1;x[i];tmp*=2) {
int num=min(tmp,x[i]);
int wt=w[i]*num,vt=v[i]*num;
for(int j=m;j>=wt;j--)
f[j]=max(f[j],f[j-wt]+vt);
x[i]-=num;
}
cout<<f[m]<<endl;
例题：宝物筛选
混合背包
将01背包、完全背包和多重背包缝合在一起的问题。
思路很简单，无需多讲解，分别考虑即可。形式为：
for(枚举物品) {
if(01背包)
01背包代码
else if(完全背包)
完全背包代码
else
多重背包代码
}
实际上，01背包和多重背包可以共用多重背包的代码，因为01背包可以当成只能取一次的多重背包。
例题：樱花
核心代码：
for(int i=1;i<=n;i++) {
if(x[i]==0) {\/\/完全背包
for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
else {\/\/01背包和多重背包
for(int tmp=1;x[i];tmp*=2) {
int num=min(tmp,x[i]);
int wt=w[i]*num,vt=v[i]*num;
for(int j=m;j>=wt;j--)
f[j]=max(f[j],f[j-wt]+vt);
x[i]-=num;
}
}
}
cout<<f[m]<<endl;
至此，基本模型已经讲完，希望读者能把每一个步骤都理解透彻！
谢谢观看
鲁ICP备2025150228号