01背包
Acwing 2. 01背包问题
状态表示：二维
集合：只从前 \(i\) 个物品里面选择总体积 \(\leq j\) 选法的集合
属性：选法价值的最大值
状态计算分为 放 \(i\) 和 不放 \(i\) （要不要把当前物品放进背包）:
- 不放 \(i\) 意味着在前 \(i-1\) 个物品里面选，且总体积不超过 \(j\)
- 放 \(i\) 的话先来看看里面应该都是些什么东西
如图所示，\(f[i][j]\) 表示的是 \(0\) 至 \(i\) 里面所有选法的权值和的最大值，我们可以将 \(f[i][j]\) 拆成两部分来看待，即 \(f[i-1][j-v[i]]\) 和 \(i\)
那么这两段的权值和为 \(f[i-1][j-v[i]]+w[i]\) ，由于求最大值，所以我们要比较一下那种选择可以使权值最大，于是我们就得到了状态转移方程
\[f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])\]
由于下标不能是负数，所以上述转移方程要求 \(j\geq w[i]\) 。当 \(j<w[i]\) 时，\(f[i][j]=f[i-1][j]\)
综上所述，可以得出：
\[f[i][j]=\left\{\begin{align}&f[i-1][j],&j<w[i] \\&max(f[i-1][j],f[i-1][j-v[i]]+w[i]),&j\geq w[i] \end{align}\right.\]
#include using namespace std;const int N = 1010;int f[N][N],v[N],w[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>v[i]>>w[i]; for(int i=1;i<=n;i++) { for(int j=0;j=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0;}注意题目给的数据，我们的数组的第二维是跟着容量的范围而不是物品数的范围
优化版本：
我们可以发现在 \(f[i][j]\) 的时候只用到了 \(f[i-1][j]\) ，这样 \(f[i-2][j]\)，\(f[i-3][j]\) …… 就被浪费掉了，而且，我们二维的状态只用到了\(j\) 和 \(j-w_i\) 都是 \(\leq j\) 不会在两侧，于是我们就可以用滚动数组来优化这个问题
首先，我们直接删除掉 \(i\) 这个状态，那么原方程就会变成：
\[f[j]=\left\{\begin{align}&f[j],&j<w[i] \\&max(f[j],f[j-v[i]]+w[i]),&j\geq w[i] \end{align}\right.\]
由于 \(f[j]=f[j]\) 是恒等式，直接删去，由于 \(max(f[j],f[j-v[i]]+w[i])\) 要求 \(j\geq w[i]\) ，所以 \(j\) 直接从 \(w[i]\) 开始枚举
好，接下来再看变形后的式子与原来的方程是否是等价的，答案是否定的
由于我们的 \(j\) 是从小到大枚举的，所以 \(j-v[i]\) 会在 \(j\) 之前被算，相当于二维的 \(f[i][j-v[i]]\) 与原来的方程不符，那么如何解决这个问题呢？ 我们可以让 \(j\) 从大到小枚举，这样就保证了当我们计算 \(f[j]\) 的时候 \(f[j-v[i]]\) 因为比 \(j\) 小，所以还没有被更新，用的就是 \(i-1\) 层的 \(f[j-v[i]]\) ，问题解决
01背包如何保证拿一次？ 那么当前背包的体积就要去找前面的，而前面的都肯定是没有拿过这个物品的，所以可以保证只拿一次。
当然我们可以边输入边计算，又可以省下数组的空间
#include using namespace std;const int N = 1010;int f[N];int main(){ int n,m; cin>>n>>m; for(int i=1;i>v>>w; for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+w); } cout<<f[m]; return 0;}完全背包
Acwing 3 完全背包问题
状态表示：二维
集合：所有只考虑前 \(i\) 个物品，且总体积 \(\leq j\) 选法的集合
属性：选法价值的最大值
状态计算以第 \(i\) 个物品选几个为划分，注意体积不能超过 \(j\) ，即 \(k×v[i]\leq j\)
注意当 \(k=0\) 时就相当于不选，所以需要从 \(0\) 开始枚举，这里还需要对 \(f[i][j]\) 打擂台，有别于01背包
我们可以得出状态转移方程
\[f[i][j]=max(f[i][j],f[i-1][j-k×v[i]]+w[i])\]
#include using namespace std;const int N = 1010;int f[N][N],v[N],w[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>v[i]>>w[i]; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); cout<<f[n][m]; return 0;}那么这样的时间复杂度大概是 \(O(m^2n)\) 的，显然不行
我们来想想如何优化
首先，将原方程展开得：
\[f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2×v[i]]+2×w[i],…)\]
然后再与 \(f[i][j-v[i]]\) 做一下对比：
\[f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2×v[i]]+w[i],…)\]
那么我们可以发现，\(f[i][j]\) 仅仅比 \(f[i][j-v[i]]\) 多了一个 \(f[i-1][j]\) ，然后后面的每一项都多一个 \(w[i]\)
于是我们就可以将 \(f[i][j-v[i]]\) 加上 \(w[i]\) 转化成 \(f[i-1][j-v[i]]+w[i],f[i-1][j-2×v[i]]+2×w[i],…\)
再与 \(f[i-1][j]\) 比较一下最大值就行了
于是我们就得到了优化后的状态转移方程
\[f[i][j]=\left\{\begin{align}&f[i-1][j],&j<w[i] \\&max(f[i-1][j],f[i][j-v[i]]+w[i]),&j\geq w[i] \end{align}\right.\]
#include using namespace std;const int N = 1010;int f[N][N],v[N],w[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>v[i]>>w[i]; for(int i=1;i<=n;i++) for(int j=0;j=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]); else f[i][j]=f[i-1][j]; } cout<<f[n][m]; return 0;}我们可以发现，这个方程跟01背包非常像，所以我们可以按照01背包的思路优化成1维
注意完全背包跟01背包唯一的区别就在于01背包是 \(f[i-1][j-v[i]]+w[i]\) 而完全背包是 \(f[i][j-v[i]]+w[i]\)
完全背包没有 -1 这个问题，所以从小到大遍历，从大到小是不行的，从大到小会使得每个物品就拿一次（参见01背包的优化）
#include using namespace std;const int N = 1010;int f[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>v>>w; for(int j=v;j<=m;j++) f[j]=max(f[j],f[j-v]+w); } cout<<f[m]; return 0;}多重背包
Acwing 4 多重背包问题I
状态表示：二维
集合：所有只从前 \(i\) 个物品中选，并且总体积 \(\leq j\) 选法的集合
属性：每一个选法对应的总价值的最大值
状态计算和完全背包非常像，不过将 \(k\) 枚举结束的条件改成 \(s\) 个
不过这样的时间复杂度很高，\(O(m^2n)\)
#include using namespace std;const int N = 105;int f[N][N];int v[N],w[N],s[N];int main(){ int n,m; cin>>n>>m; for(int i=1;i>v[i]>>w[i]>>s[i]; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=s[i]&&k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k); cout<<f[n][m]; return 0;}然后我们尝试优化，既然和完全背包很像，我们先来试试通过完全背包的方式优化
首先将原方程展开得：
\[f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2×v[i]]+2×w[i],…,f[i-1][j-s[i]×v[i]]+s[i]×w[i])\]
再对比 \(f[i][j-v[i]]\) ：
\[f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2×v[i]]+w[i],…,f[i-1][j-s[i]×v[i]]+(s[i]-1)w[i],f[i-1][j-(s[i]+1)w[i]]+s[i]×w[i])\]
我们发现两个式子很像，不过，\(f[i][j-v[i]]\) 多了一项 \(f[i-1][j-(s[i]+1)w[i]]+s[i]×w[i])\) ，我们不可以通过前 \(n\) 个数的最大值和最后一个数，求出前 \(n-1\) 个数的最大值，所以这样的方法是不可行的
我们可以用二进制的方式来优化
例如当 \(s=1023\) 时，我们真的需要从 \(0\) 枚举到 \(1023\) 吗？
我们可以将若干个 \(i\) 个物品打包，比如说我们可以打包成10组：\(1,2,4,8,…512\)
每组最多选一次，我们可以用这10组凑出来 \(0\) 到 \(1023\) 的任何数（二进制可以表示出所有的十进制整数）
那么对于任何一个 \(s\)，我们将物品打包成 \(2^0,2^1,2^2,…,2^k\)，\(2^0\) 一直加到 \(2^k \leq s\)
如果 \(2^0\) 一直加到 \(2^k < s\)，再补上一个 \(c\)
那么显然有 \(c<2^{k+1}\)
那么来证明一下是不是这样就能表示出 \(0\) 到 \(s\) 的所有数？
首先，\(2^0\) 一直加到 \(2^k\) 能凑出 \(0\) 到 \(2^{k+1}-1\) 的所有数（等比数列公式）
补上 \(c\) 以后便能凑出 \(0\) 到 \(2^{k+1}+c\) 的所有数，\(2^{k+1}+c\) 即 \(s\)
所以是可行的，我们将原本的 \(O(m^2 n)\) 优化到了 \(O(m^2 logn)\)
转化完之后再求一遍01背包就行了
注意我们的打包时数组体积的部分要开 \(log_2 2000×1000\) \(log_22000\) 要上取整得 \(12\)
#include using namespace std;const int N = 25000;int n,m;int v[N],w[N],f[N];int main(){ cin>>n>>m; int cnt=0; //重新打包后物品的个数 for(int i=1;i>a>>b>>s; int k=1; //2的k次幂 while(k0) { cnt++; v[cnt]=a*s; w[cnt]=b*s; } } n=cnt; for(int i=1;i=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout<<f[m]; return 0;}其实还有单调队列的优化方式，不过是提高的内容，等我之后滚回来更新
分组背包
Acwing 9 分组背包问题
状态表示：二维
集合：只从前 \(i\) 个物品里面选，且总体积 \(\leq j\) 的所有选法
属性：选法价值的最大值
状态计算：枚举第 \(i\) 组，物品选第几个或不选
不选也就是 \(f[i-1][j]\)
选第 \(k\) 个也就是 \(f[i-1][j-v[i][k]]+w[i][k]\)
注意 \(k\) 枚举的是下标，所以从0开始
#include using namespace std;const int N = 105;int f[N][N],v[N][N],w[N][N],s[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>s[i]; for(int j=0;j>v[i][j]>>w[i][j]; } for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { f[i][j]=f[i-1][j]; for(int k=0;k<s[i];k++) { if(v[i][k]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); } } } cout<<f[n][m]; return 0;}直接删去一维，得到状态转移方程
\[f[j]=max(f[j],f[j-v[i][k]]+w[i][k]),1\leq k\leq s[i]\]
#include using namespace std;const int N = 105;int f[N],s[N],v[N][N],w[N][N];int n,m;int main(){ cin>>n>>m; for(int i=1;i>s[i]; for(int j=0;j>v[i][j]>>w[i][j]; } for(int i=1;i=0;j--) for(int k=0;k<s[i];k++) if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); cout<<f[m]; return 0;}混合背包
Acwing 7 混合背包问题
此为几种背包的模型（01背包、多重背包、完全背包）的综合使用，所以如果弄懂了前几种背包模型，混合背包的问题也会迎刃而解，这里主要介绍一种写法使得代码可读性变高
首先我们知道多重背包实际上是转化为01背包来做的，所以我们如果遇到多重背包时，我们直接将它加进去，最后当作01背包解决就行了
在代码中，我使用了结构体，一个是物品的种类，另外两个是体积和权值
输入多重背包的时候，直接二进制优化好再加进 vector 就行了
最后根据物品类型的不同分别处理就行了
#include #include using namespace std;const int N = 1010;int f[N];struct Thing{ int kind,v,w;};vector things;int main(){ int n,m; cin>>n>>m; for(int i=1;i>v>>w>>s; if(s==-1) things.push_back({0,v,w}); else if(s==0) things.push_back({1,v,w}); else { int k=1; while(k0) things.push_back({0,v*s,w*s}); } } for(auto thing:things) { if(thing.kind==0) { for(int j=m;j>=thing.v;j--) { f[j]=max(f[j],f[j-thing.v]+thing.w); } } else { for(int j=thing.v;j<=m;j++) { f[j]=max(f[j],f[j-thing.v]+thing.w); } } } cout<<f[m]; return 0;}