复健\(Day1\)
今天复习基础背包问题，在\(ACWing\)上使用挑战模式去打模板，提高打代码速度
\(01\)背包
解决每种物品只有一样的情况
时间复杂度\(O(nV)\)，空间复杂度优化后为\(O(V))\)
空间优化的代码中体积一维从后往前更新，因为其递推公式为\(dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])\)，若我们从前往后更新那么相当于改变了\(dp[i-1][j-v[i]]\)的值，这样会对后面的更新造成影响
#include<iostream>
#include<cstdio>
#define maxn 1010
using namespace std;
int dp[maxn],v[maxn],w[maxn];
int n,V;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
printf("%d\n",dp[V]);
return 0;
}
多重背包
解决每种物品有确定值的情况
二进制优化
进行二进制优化后，时间复杂度由\(O(nVs)\)优化为\(O(nVlogs)\)
之所以能进行二进制优化的原因：对于某种数量\(s\)，我们不需要从\(0\)开始枚举其选择的数量，而是采用分组打包的方式\(:2\ ^0,2\ ^1,...2\ ^k\)，直至\(s-2\ ^k+1\leqslant 0\)时，无法再用\(2\ ^t\)的形式表示，那么最后一组就为\(s-2\ ^k+1\)个，这样我们的枚举数就从原本的\(s\)优化为了\(logs\)了
体积一维从后往前更新，因为其递推公式为\(dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])\)
#include<iostream>
#include<cstdio>
#define maxn 2010
using namespace std;
int dp[maxn],v[maxn],w[maxn],s[maxn],nv[maxn],nw[maxn],cnt;
int n,V;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
int k;
for(k=1;s[i]-(1<<k)+1>=0;k++)
{
nv[++cnt]=v[i]*(1<<(k-1));
nw[cnt]=w[i]*(1<<(k-1));
}
k--;
nv[++cnt]=v[i]*(s[i]-(1<<k));
nw[cnt]=w[i]*(s[i]-(1<<k));
}
for(int i=1;i<=cnt;i++)
{
for(int j=V;j>=nv[i];j--) dp[j]=max(dp[j],dp[j-nv[i]]+nw[i]);
}
printf("%d\n",dp[V]);
return 0;
}
优先队列优化
https://www.acwing.com/solution/content/53507/
上面是写的很清楚的解析
滚动数组的长度为\(s[i]+1\)，所有满足\(j\equiv r(modv[i])\)进行维护从而得出最大值
最后时间复杂度为\(O(nV)\)，空间复杂度为\(O(v)\)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1010,M=20010;
int g[M],f[M],q[M];
int v[N],w[N],s[N];
int n,V;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
{
memcpy(g,f,sizeof(g));
for(int r=0;r<v[i];r++)
{
int hh=0,tt=-1;//每次都是新的队列
for(int j=r;j<=V;j+=v[i])
{
while(hh<=tt&&j-q[hh]>s[i]*v[i]) hh++;//最开头那个f值最大的v，我们的j减去它之后剩余的体积过大，其实没必要存，所以出队
while(hh<=tt&&g[q[tt]]+(j-q[tt])/v[i]*w[i]<=g[j]) tt--;//最后的那个元素并不比g[j]优，无法更新别的元素，所以出队
q[++tt]=j;
f[j]=g[q[hh]]+(j-q[hh])/v[i]*w[i];//更新最前端的那个元素
}
}
}
printf("%d\n",f[V]);
return 0;
}
完全背包
解决物品数量为无穷多个的情况
时间复杂度为\(O(nV)\)，空间复杂度优化为\(O(V)\)
它的体积一维从前往后更新，原因是递推公式为\(dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])\)它是由\(dp[i][j-v[i]]+w[i]\)更新而来，所以我们要先更新小的\(j\)，这样才能进一步更新后面的\(j\)
#include<iostream>
#include<cstdio>
#define maxn 2010
using namespace std;
int dp[maxn],v[maxn],w[maxn];
int n,V;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=V;j++) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
printf("%d\n",dp[V]);
return 0;
}
混合背包
很简单的，这种情况就是判断此种物品是有一个还是有确定个，还是有无穷多个，使用不同处理即可
#include<iostream>
#include<cstdio>
#define maxn 1010
using namespace std;
int dp[maxn],v[maxn],w[maxn],s[maxn],nv[maxn],nw[maxn],cnt;
int n,V;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i]>>s[i];
if(s[i]==-1)
{
for(int j=V;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
else if(s[i]==0)
{
for(int j=v[i];j<=V;j++) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
else
{
int k;
cnt=0;
for(k=1;s[i]-(1<<k)+1>0;k++)
{
nv[++cnt]=v[i]*(1<<(k-1));
nw[cnt]=w[i]*(1<<(k-1));
}
k--;
nv[++cnt]=v[i]*(s[i]-(1<<k)+1);
nw[cnt]=w[i]*(s[i]-(1<<k)+1);
for(int j=1;j<=cnt;j++)
{
for(int m=V;m>=nv[j];m--) dp[m]=max(dp[m],dp[m-nv[j]]+nw[j]);
}
}
}
printf("%d\n",dp[V]);
return 0;
}