动态规划（1）——背包九讲

\(1.\)\(01\)背包

    for(int i=1;i<=n;++i)
    {
        for(int j=v;j>=a[i].v;--j)//将容量从大到小枚举，避免了一个物品被使用多次的情况（因为容量比它小的还未被更新价值）
        {
            f[j]=max(f[j],f[j-a[i].v]+a[i].w);
        }
    }

\(2.\)完全背包

    for(int i=1;i<=n;++i)
    {
        for(int j=a[i].v;j<=v;++j)//将容量从小到大枚举，每个物品都可以被选多次
        {
            f[j]=max(f[j],f[j-a[i].v]+a[i].w);
        }
    }

\(3.\)多重背包

（常见的两种优化：二进制优化，单调队列优化）

    //二进制优化
    int tot=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&a[i].v,&a[i].w,&a[i].num);
    }
    for(int i=1;i<=n;++i)
    {
        int k=1;
        while(k<=a[i].num)
        {
            w[++tot]=a[i].w*k;
            v[tot]=a[i].v*k;
            k<<=1;
            a[i].num-=k;
        }
        if(a[i].num)
        {
            w[++tot]=a[i].w*a[i].num;
            v[tot]=a[i].v*a[i].num;
        }
    }
    for(int i=1;i<=tot;++i)
    {
        for(int j=v;j>=v[i];--j)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

\(4.\)混合三种背包

    for(int i=1;i<=n;++i)
    {
        if(a[i].num)//01背包和多重背包
        {
            for(int j=1;j<=a[i].num;++j)
            {
                for(int v=V;v>=a[i].v;--v)
                {
                    f[v]=max(f[v],f[v-a[i].v]+a[i].w);
                }
            }
        }
        else if(!a[i].num)//完全背包
        {
            for(int v=a[i].v;v<=V;++v)
            {
                f[v]=max(f[v],f[v-a[i].v]+a[i].w);
            }
        }
    }

\(5.\)二维费用的背包问题

    for(int i=1;i<=n;++i)
    {
        for(int j=V;j>=v[i];--j)
        {
            for(int k=M;k>=m[i];--k)
            {
                f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]);
            }
        }
    }

\(6.\)分组背包

    for(int k=1;k<=n;++k)//有n组背包
    {
        for(int j=v;j>=0;--j)
        {
            for(int i=1;i<=c[k][0];++i)
            {
                if(j>=v[c[k][i]])
                {
                    f[j]=max(f[j],f[j-v[c[k][i]]]+w[c[k][i]]);//因为一组中只能选一个
                }
            }
        }
    }

\(7.\)有依赖的背包问题[需要区别于分组背包]

当依赖关系很多时，直接上树上背包（因为依赖关系会构成森林）

当较少时（如\(noip2006\)金明的预算方案）

    for(int i=1;i<=n;++i)//所有物品
    {
        if(!a[i].p)//是主件
        {
            for(int j=0;j<a[i].v;++j) t[j]=f[j];
            for(int j=a[i].v;j<=V;++j) t[j]=max(t[j],f[j-a[i].v]+a[i].w);
            for(int j=1;j<=n;++j)
            {
                if(a[j].p==i)
                {
                    for(int v=V;v>=a[i].v+a[j].v;--v)
                    {
                        t[v]=max(t[v],t[v-a[j].v]+a[j].w);
                    }
                }
            }
            for(int j=1;j<=V;++j) f[j]=max(f[j],t[j]);
        }
    }

\(8.\)泛化物品

\(9.\)背包问题问法的变化：

（1）输出最优方案

法一：

与一般的动态规划问题输出方案相似，每一部分动态规划的时候，另开一个数组来记录这一步的答案是由谁推出来的

法二：

在输出时，检验是否\(f[i] [v]==f[i-1] [v-a[i].v]+a[i].w\);

    for(int i=1;i<=n;++i)
    {
        for(int v=V;v>=a[i].v;--v)
        {
            if(f[i-1][v-a[i].v]+a[i].w>f[i-1][v]) f[i][v]=f[i-1][v-a[i].v]+a[i].w,g[i][v]=1;
            else f[i][v]=f[i-1][v],g[i][v]=0
        }
    }

    int i=n;
    int v=V;
    while(i>0)
    {
        if(g[i][v]==0) continue;
        else if(g[i][v]==1)
        {
            printf("%d\n",i);
            v-=a[i].v;
        }
    }

\(（2）\)输出字典序最小的方案

    int n,v;
    scanf("%d%d",&n,&v);
    for(int i=n;i>=1;--i)//注意这里是逆序输入的
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=v;j>=v[i];--j)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    int V=v;
    for(int i=n;i>=1;--i)
    {
        if(f[V]==f[V-v[i]]+w[i])
        {
            printf("%d\n",n-i+1);
            V-=v[i];
        }
    }

\(（3）\)输出方案总数

    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    f[0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=a[i];j<=num;++j)
        {
            f[j]+=f[j-a[i]];
        }
    }

\(（4）\)最优方案的总数

\(（5）\)求解次优解，k优解.

\[f[v_i][1\cdots k]=max(f[v_i][1\cdots k],f[v_i-a[i].v][1\cdots k]+a[i].w)\]

    for(int i=1;i<=n;++i) scanf("%d%d",&a[i].v,&a[i].w);
    for(int i=1;i<=n;++i)
    {
        for(int j=v;j>=a[i].v;--j)
        {
            int c1=1,c2=1,cnt=0;
            while(cnt<k)
            {
                if(f[j][c1]>f[j-a[i].v][c2]+a[i].w) g[++cnt]=f[j][c1++];
                else g[++cnt]=f[j-a[i].v][c2++]+a[i].w;//任意两个取max的运算都相当于两个有序队         }                                          //列的合并
            for(int c=1;c<=k;++c)
            {
                f[j][c]=g[c];
            }
        }
    }

因为任意两个背包都不能完全相同，故

    memset(f,128,sizeof(f));//将f赋值为了一个负的极大值（-2139062144），虽然它看起来像是赋的正值
    f[0][1]=0;//v为1的最优解为0

\(ex:\)

树上背包：似乎只需要加一个\(dfs\)就可以了

    int sz[maxn];
    void dfs(int u)
    {
        sz[u]=1;
        for(int i=head[u];i;i=ed[i].nxt)
        {
            int v=ed[i].to;
            dfs(v);
            sz[u]+=sz[v];
            for(int j=sz[u];j>=k;--j)
            {
                for(int k=0;k<=sz[v];++k)
                {
                    f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]);
                }
            }
        }
    }

初始化为：

    for(int i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
        f[i][1]=v[i];
    }

动态规划（1）——背包九讲

原文：https://www.cnblogs.com/iwillenter-top1/p/11823093.html