【5】背包类型动态规划学习笔记

· · 算法·理论

前言

学习了简单背包DP，这一篇博客主要是讲背包问题进阶。所以这篇博客的难度系数很有可能不止 5 级，个人评价是 6 级。所以在基础背包部分不会讲太多，会直接使用一维背包。

基础背包

01背包

给定 n 个物品，一个容量为 V 的背包，每件物品只能用一次，有两个属性：体积 a_{i} 和价值 b_{i} ，求能得到的最大价值。

设 dp[j] 表示容量为 j 的背包的最大价值，目前枚举到第 i 个物品，则dp方程为：

dp[j]=max\{dp[j],dp[j-a[i]]+b[i]\}

其中， dp[j] 表示不选第 i 个物品， dp[j-a[i]]+b[i] 表示选第 i 个物品，然后选择最大值就可以了。

模板如下：

for(int i=1;i<=m;i++)
    for(int j=t;j>=c[i];j--)
       f[j]=max(f[j],f[j-c[i]]+w[i]);

注意此时对于 j 一定要倒序枚举，以保证每次转移都是没有更新后的值。

时间复杂度： O(nV)

完全背包

给定 n 个物品，一个容量为 V 的背包，每件物品能用无限次，有两个属性：体积 a_{i} 和价值 b_{i} ，求能得到的最大价值。

设 dp[j] 表示容量为 j 的背包的最大价值，目前枚举到第 i 个物品，则dp方程为：

dp[j]=max\{dp[j],dp[j-a[i]]+b[i]\}

没错，和01背包一模一样。

模板如下：

for(int i=1;i<=m;i++)
    for(int j=c[i];j<=t;j++)
       f[j]=max(f[j],f[j-c[i]]+w[i]);

注意此时对于 j 要正序枚举，每次转移时是更新过的值，可以使每个物品使用多次。

时间复杂度： O(nV)

满背包

给定 n 个物品，一个容量为 V 的背包，背包必须装满，每件物品只能用一次，有两个属性：体积 a_{i} 和价值 b_{i} ，求能得到的最大价值。

设 dp[j] 表示容量为 j 的背包的最大价值，目前枚举到第 i 个物品，则dp方程为：

dp[j]=max\{dp[j],dp[j-a[i]]+b[i]\}

没错，还是和01背包一模一样。

模板如下：

for(int i=1;i<=t;i++)f[i]=-99999999;
f[i]=0;
for(int i=1;i<=m;i++)
    for(int j=t;j>=c[i];j--)
       f[j]=max(f[j],f[j-c[i]]+w[i]);

由于必须装满的原因，把未使用的空缺赋上负无穷，表示不能从此处转移，保证没有空余。

时间复杂度： O(nV)

基础例题

例 1 ：

P1048 [NOIP2005 普及组] 采药

01背包模板题，不多赘述。

#include <bits/stdc++.h>
using namespace std;
int c[2000],w[2000],f[2000];
int main()
{
    int t,m;
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&c[i],&w[i]);
    for(int i=1;i<=m;i++)
        for(int j=t;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%lld",f[t]);
    return 0;
}

例 2 ：

P1616 疯狂的采药

完全背包模板题，不多赘述。

#include <bits/stdc++.h>
using namespace std;
long long c[20000000],w[20000000],f[20000000];
int main()
{
    long long t,m;
    scanf("%lld%lld",&t,&m);
    for(long long i=1;i<=m;i++)
        scanf("%lld%lld",&c[i],&w[i]);
    for(long long i=1;i<=m;i++)
        for(long long j=c[i];j<=t;j++)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%lld",f[t]);
    return 0;
}

例 3 ：

P1049 [NOIP2001 普及组] 装箱问题

由于没有价值，题目要求的是最大体积，所以把体积直接看成价值，然后就是01模板了。

#include <bits/stdc++.h>
using namespace std;
int n,v,t[30000],f[30000];
int main()
{
    scanf("%d",&v);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&t[i]);
    for(int i=0;i<n;i++)
        for(int j=v;j>=t[i];j--)
            f[j]=max(f[j],f[j-t[i]]+t[i]);
    printf("%d",v-f[v]);
    return 0;
}

例 4 ：

P1855 榨取kkksc03

在原先体积限制的基础下，增加了金钱限制。设状态 dp[j][k] 表示体积容量为 j ，金钱容量为 k 的背包的最大价值，目前枚举到第 i 个物品，则dp方程为：

dp[j][k]=max\{dp[j][k],dp[j-a[i]][k-b[i]]+1\}

其中， dp[j][k] 对应不选的情况， dp[j-a[i]][k-b[i]]+1 对应选的情况。

#include <bits/stdc++.h>
#define INF 999999999
using namespace std;
int n,m,t,a[300],b[300],f[300][300];
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=0;i<n;i++)
        scanf("%d%d",&a[i],&b[i]);
    for(int i=0;i<n;i++)
        for(int j=m;j>=a[i];j--)
            for(int k=t;k>=b[i];k--)
                f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+1);
    printf("%d",f[m][t]);
    return 0;
}

例 5 ：

P1164 小A点菜

设状态 dp[j] 表示容量为 j 的背包的方法数，则转移方程为：

dp[j]=dp[j]+dp[j-w[i]]

其中， dp[j] 表示不选的方法数， dp[j-w[i]] 表示选的方法数，合起来就是总的方法数。

注意题目中

一定刚好把 uim 身上所有钱花完

所以是满背包，代码中是另一种实现方式：

#include <bits/stdc++.h>
using namespace std;
int t,m,f[20000],w[20000]; 
int main()
{
    scanf("%d%d",&m,&t);
    for(int i=1;i<=m;i++)scanf("%d",&w[i]);
    f[0]=1;
    for(int i=1;i<=m;i++)
        for(int j=t;j>=w[i];j--)
            if(f[j-w[i]]!=0)f[j]=f[j]+f[j-w[i]];
    printf("%d",f[t]);        
    return 0;
}

进阶背包

分组背包

给定 n 个物品，一个容量为 V 的背包，每件物品只能用一次，有三个属性：体积 a_{i} ，价值 b_{i} 和组数 c_{i} ，每组物品相互冲突，求能得到的最大价值。

设 dp[j] 表示容量为 j 的背包的最大价值，目前枚举到第 i 组的第 k 个物品,则dp方程为：

dp[j]=max\{dp[j],dp[j-a[c[i][k]]]+b[c[i][k]]\}

避免冲突的方法，就是每次枚举组数，然后在枚举 j 的时候遍历一遍组中的元素，进行选择。由于只有在各个组中的元素枚举完后会覆盖或不影响 dp[j] ，所以可以保证每个组中的元素只使用一个。

模板如下：

for(int i=0;i<=2000;i++)
    {
    int l=c[i].size();
    if(l==0)continue;
    for(int j=m;j>=0;j--)
        for(int k=0;k<l;k++)
           if(j>=a[c[i][k]])f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);
    }

时间复杂度： O(nV)

多重背包

给定 n 个物品，一个容量为 V 的背包，每件物品只能用一次，有三个属性：体积 a_{i} ，价值 b_{i} 和数量 c_{i} ，求能得到的最大价值。

朴素求法：

按照朴素01背包来做，每次枚举数量，时间复杂度如下：

O(nV\sum_{i=0}^{n}c[i])

很明显，复杂度非常高，需要考虑优化。

二进制拆分优化：

还记得在 【6】ST表学习笔记 中提到过的 倍增 思想吗？

倍增思想常用来优化算法的时空复杂度，和其他算法搭配使用。

其实，二进制拆分也是一种倍增。

首先，考虑将数量拆分成 2^0 ， 2^1 ， 2^2 ...... 2^k 等 2 的非负整数幂，这样就可以凑出 2^{k+1}-1 中所有的重量。为什么呢？因为任何一个 [1, 2^{k+1}-1] 的数，都可以用 k+1 位二进制位表示出来。而每一位二进制位，就是对应 2^0 ， 2^1 ， 2^2 ...... 2^k 。

例如，当 k=3 , 要表示的数是 13 时， 13 的二进制是这样的：

(13)_{10}=(1101)_{2}

也就是

13=2^3+2^2+2^0

那拆分的数拆不尽怎么办？设拆分的数为 n ，还是考虑将数量拆分成 2^0 ， 2^1 ， 2^2 ...... 2^k ，则可以表示的部分是 [1, 2^{k+1}-1] ，剩余部分恰好是 n-2^{k+1}+1 ，将剩余部分加入上一个区间，就得到了 [1, n] 。

代码如下：

int now=0;
for(int j=1;now<=e[d[i]];j*=2)
    if(now+j<=e[d[i]])c1[++q]=d[i]*j,now+=j;
    else break;
if(e[d[i]]>now)c1[++q]=(e[d[i]]-now)*d[i];

代码中 now 是目前可以表示的量的范围，表示 2^{k+1}-1 ，在最后减去这个范围，就是拆分剩余的数。

时间复杂度如下：

O(nV\sum_{i=0}^{n}\log c[i])

单调队列优化：

听说可以做到 O(nV) ，但是我不会。

进阶例题

例 6 ：

P1757 通天之分组背包

分组背包模板题，不多赘述。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=0,a[2000],b[2000],f[2000];
vector<int>c[2000]; 
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        {
            int d;
            scanf("%d%d%d",&a[i],&b[i],&d);
            c[d].push_back(i);
        }
    for(int i=0;i<=2000;i++)
        {
        int l=c[i].size();
        if(l==0)continue;
        for(int j=m;j>=0;j--)
            for(int k=0;k<l;k++)
                if(j>=a[c[i][k]])f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);
        }
    for(int i=0;i<=m;i++)
        ans=max(ans,f[i]);
    printf("%d",f[m]);
    return 0;
}

例 7 ：

CF864E Fire

这题在01背包下增加了一个限制：时限 d_{i} 。 很明显，对于时限较短的物品，可以优先处理；而对于时限较长的物品，可以放在后面处理。换句话说，如果优先处理时限较短的物品，既可以处理时限较短的物品，也可以处理时限较长的物品，而反之则不能。因此，可以贪心+背包，先把物品按照 d_{i} 递增排序，然后使用背包DP求解。

设 dp[j] 表示容量为 j 的背包的最大价值，目前枚举到第 i 个物品，则dp方程为：

dp[j]=max\{dp[j],dp[j-a[i]]+b[i]\}

另外，此题要求输出带走的物品。可以使用STL中的 vector 来存储可以带走的物品。如果在转移的过程中，发现 dp[j-a[i]]+b[i]\gt dp[j] ，证明选择了第 i 个物品，要把 j-a[i] 的带走的物品直接复制到 dp[j] 的带走的物品并添加上第 i 个物品。

#include <bits/stdc++.h>
using namespace std;
struct item
{
    int t,d,p,h;
}a[200];
int n,k,ans=0,f[5000],q=0;
vector<int>b[5000];
bool cmp(struct item a,struct item b)
{
    return a.d<b.d;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        {
        scanf("%d%d%d",&a[i].t,&a[i].d,&a[i].p);
        a[i].h=i;
        k=max(k,a[i].d);
        }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=a[i].d-1;j>=a[i].t;j--)
            if(f[j-a[i].t]+a[i].p>f[j])
                {
                f[j]=f[j-a[i].t]+a[i].p;
                b[j].clear();
                b[j]=b[j-a[i].t];
                b[j].push_back(a[i].h);
                }
    for(int i=0;i<=k;i++)
        if(f[i]>ans)ans=f[i],q=i;
    printf("%d\n",ans);
    int l=b[q].size();
    printf("%d\n",l);
    for(int i=0;i<l;i++)
        printf("%d ",b[q][i]);
    printf("\n");
    return 0;
}

例 8 ：

P1417 烹调方案

如果要先选第 i 个物品优于第 j 个物品，则必有以下式子：

a_{i}+a_{j}-c_{i}\times b_{j} \gt a_{j}+a_{i}-c_{j}\times b_{i}

移项抵消得

-c_{i}\times b_{j} \gt -c_{j}\times b_{i}

去掉负号得

c_{i}\times b_{j} \lt c_{j}\times b_{i}

所以把物品按照 c_{i}\times b_{j} 升序排序，再进行一次01背包就可以了。

#include <bits/stdc++.h>
using namespace std;
struct item
{
    int a,b,c;
}a[200];
int n,t,ans=0,f[100010];
bool cmp(struct item a,struct item b)
{
    return (long long)b.b*a.c<(long long)a.b*b.c;
}

int main()
{
    scanf("%d%d",&t,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].a);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=t;j>=a[i].c;j--)
            if(a[i].a-(long long)j*a[i].b>0)f[j]=max(f[j],(int)(f[j-a[i].c]+a[i].a-(long long)j*a[i].b));
            else f[j]=max(f[j],f[j-a[i].c]);
    for(int i=0;i<=t;i++)
        ans=max(f[i],ans);
    printf("%d",ans);
    return 0;
}

例 9 ：

CF366C Dima and Salad

由

\sum^{m}_{j=1}a_j\div \sum^{m}_{j=1}b_j=k

移项得

\sum^{m}_{j=1}a_j =k\sum^{m}_{j=1}b_j

将 k 放进 \sum 里得到

\sum^{m}_{j=1}a_j =\sum^{m}_{j=1}kb_j

移项得

\sum^{m}_{j=1}a_j -\sum^{m}_{j=1}kb_j=0

把 \sum 提出来得

\sum^{m}_{j=1}(a_j -kb_j)=0

问题就转换为了每个物品体积为 a_j -kb_j ，价值为 b_j 的体积为 0 的01背包。

由于体积 a_j -kb_j 可能有负数，所以分两个数组存储。

#include <bits/stdc++.h>
using namespace std;
int n,k,a[300],b[300],f[10020],g[10020],ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=10001;i++)f[i]=-99999,g[i]=-99999;
    for(int i=0;i<n;i++)
        {
        int c=a[i]-k*b[i];
        if(c>=0)
            for(int j=10000;j>=c;j--)
                f[j]=max(f[j],f[j-c]+a[i]);
        else 
            for(int j=10000;j>=-c;j--)
                g[j]=max(g[j],g[j+c]+a[i]);
        }
    for(int i=0;i<=10000;i++)
        ans=max(ans,f[i]+g[i]);
    if(ans!=0)printf("%d",ans);
    else printf("-1");
    return 0;
}

例 10 ：

CF755F PolandBall and Gifts

由于

有 n 个人要互相送礼物

可以知道，如果把 x 想送 y 礼物看作一条 x\to y 的有向边，最终一定会形成若干个环。

对于最大的情况，可以使用贪心。由题目中

一个人能收到礼物，当且仅当她带了礼物，并且应该送给她礼物的人也带了礼物。

所以如果要最大化收不到礼物的人数，可以隔一个人没带一次，这样一次就有两个人收不到礼物。对于人数为偶数的环（以后简写为偶环），可以刚刚好隔一个人没带一次；对于人数为奇数的环（以后简写为奇环），会多出一个人来，如果这个人没带，只会有一个人收不到礼物。所以对于奇环多余的人，可以放在后面处理。优先处理偶环以及奇环中能一次有两个人收不到礼物的人，再处理奇环中多出来的人。

对于最小化的情况，可以使一整个环的人都没带礼物。这样就可以使每个没带礼物的人只能对答案产生 1 的贡献。对于多余的人，可以将他们排在一起，这样只有最后一个人要送礼物的人会因为送他礼物的人没带而无法收到礼物。如果刚刚好有若干个环人数和 k ，则最少有 k 个人无法收到礼物；否则就最后一个人一定会使另一个人无法收到礼物，答案为 k+1 。

判断是否有若干个环人数和 k ，使用01背包就行了。参考例 3 就行。

注意这里每个环的数量可能出现多次，实质上是一个多重背包。朴素做法会超时，要进行二进制拆分优化。

#include <bits/stdc++.h>
using namespace std;
int n,k,p,q,l,a[1000020],vis[1000020],c[1000020],c1[1000020],f[1000020],book[1000020],d[1000020],e[1000020]; 
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int dfs(int s,int now,int cnt)
{
    vis[now]=1;
    if(s==now&&cnt!=1)return cnt-1;
    else dfs(s,a[now],cnt+1);
}

void least()
{
    for(int i=1;i<=p;i++)
        if(!book[c[i]])d[++l]=c[i],book[c[i]]=1,e[c[i]]++;
        else e[c[i]]++;
    for(int i=1;i<=l;i++)
        {
        int now=0;
        for(int j=1;now<=e[d[i]];j*=2)
            if(now+j<=e[d[i]])c1[++q]=d[i]*j,now+=j;
            else break;
        if(e[d[i]]>now)c1[++q]=(e[d[i]]-now)*d[i]; 
        }
    for(int i=1;i<=k;i++)f[i]=-99999999;
    for(int i=1;i<=q;i++)
        for(int j=k;j>=c1[i];j--)
            f[j]=max(f[j],f[j-c1[i]]+c1[i]);
    if(f[k]>=0)printf("%d ",k);
    else printf("%d ",k+1);
}

void most()
{
    int h=0,cnt=0;
    bool flag=0;
    for(int i=1;i<=p;i++)
        {
        if(h+c[i]/2<=k)h+=c[i]/2;
        else 
           {
           h=k;
           flag=1;
           }
        if(c[i]%2)cnt++;
        }
    h*=2;
    if(flag==0)h+=min(k-h/2,cnt);
    printf("%d",h);
}

int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)
         if(!vis[i])c[++p]=dfs(i,i,1);
    least();
    most();
    return 0;
}

后记

也没什么好说的，DP之难难于上青天。