JZTXT

背包问题

发布时间 2023-04-09 23:41:53作者: dolires

复健\(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;
}