『学习笔记』动态规划 - 背包问题

仙山有茗 · 2022-05-18 21:59:28 · 个人记录

有 n 件物品，每件物品有一个占用空间 v_i 和一个价值 w_i。现在有一个空间为 V 的背包，求能装下物品的最大价值。

这类题就是典型的 01 背包问题。

01 背包

01 背包中，01 的意思就是每种物品有选与不选两种方案。

我们可以定义状态 f_{i,j} 为：用前 i 个物品，用 j 单位个空间，能装下的最大价值。

那么第 i 件物品可以考虑选与不选，在使用 j 单位个空间的情况下：

• 选第 i 个物品，那么 f_{i,j}=f_{i-1,j-v_i}+w_i。为什么要取用前 i-1 个物品，填满 j-v_i 的最大价值呢？因为要选择第 i 个物品，用 j 个单位空间时，需要有 v_i 个空间剩余，同时也要是最大价值。这个值再加上第 i 个物品的价值，就是选择第 i 个物品下的 f_{i,j} 了。
• 不选第 i 个物品，那么 f_{i,j} 只需要取 f_{i-1,j} 即可。不需要任何变化。

那么什么时候选第 i 个物品，什么时候不选呢？

当然是取选与不选的最大价值中的较大值了。

还要注意一下，当 j \leq v_i 时，则不能选第 i 个物品，总不能用负数的空间吧。

那么在 j>v_i 时的状态转移方程就是 f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}，否则 f_{i,j}=f_{i-1,j}。

现在来看道题吧！

P1048 采药

题目大意

有 n 株草药，每株草药有一个采摘所需的时间 v_i 和这株草药的价值 w_i，你有 V 单位时间。

在限定的时间内，采到的草药的最大价值是多少？

思路

01 背包板子。

我们把每株草药看作物品，把采摘所需时间看作重量，价值看作物品的价值，限定的时间 V 看作背包容量即可。

代码

#include <iostream>
using namespace std;
const int N=1e3+5;
int n,V,ans=-1; // 草药株数和时间限制，ans 记录答案
int v[N],w[N]; // 每株草药的时间和价值
int f[N][N]; // dp 数组

int main(){
    scanf("%d%d",&V,&n)
    for(int i=1; i<=n; i++) scanf("%d%d",&v[i],&w[i]);
    for(int i=1; i<=n; i++) // 用前 i 株草药
        for(int j=1; j<=V; j++) // 用 j 时间
            // 可以选择第 i 株草药
            if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); // 转移方程
            else f[i][j]=f[i-1][j]; // 不能选择第 i 株草药
    for(int i=1; i<=V; i++) ans=max(ans,f[n][i]); // 使用不同时间采摘到的价值总和并不一定是升序的，所以要取最大值
    printf("%d\n",ans);
    return 0;
}

滚动数组优化

通过代码中的转移方程可以发现，f_{i,j} 就只和 f_{i-1,j} 有关，于是可以考虑滚动数组。

先来尝试把上面的代码的一部分等价替换一下：

for(int i=1; i<=n; i++)
    for(int j=1; j<=V; j++)
        if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
        else f[j]=f[j];

可以发现 else 里的部分可以直接去掉，去掉后你会发现 j 从 1 循环到 v_i-1 的那一段都是无用的，因为只有当 j \geq v_i 时才会执行操作。

于是 j 可以直接从 v_i 开始循环，去掉判断条件：

for(int i=1; i<=n; i++)
    for(int j=v[i]; j<=V; j++)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

但是你这么跑一边样例，WA 了。

为什么呢？我们把滚动数组的方程换成原来的看看：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])。

我们注意到 f_{i-1,j-v_i}。如果你的 j 是从小到大的，那么你在更新一个 j 比较大的 f_{i,j} 时，需要用到 f_{i-1,j-v_i}，但是在滚动数优化下，你之前已经更新过 f_{j-v_i} 了，变成了 f_{i,j-v_i} 了。所以你更新 f_j 时取的其实是 f_{i,j-v_i}，而不是想要的 f_{i-1,j-v_i}。

举个例子吧，例如你正在更新 f_7，而更新 f_7，需要取 f_{i-1,7-3}，但你之前更新过 f_{7-3} 了，f_{7-3} 由原来的 f_{i-1,7-3} 变成了 f_{i,7-3}，所以没取到 f_{i-1,7-3}。

那么针对这个问题，怎么解决呢？

很简单，你的 j 从大到小循环就行了。更新大 j 时，需要用到 j-v_i，而你的小 j 暂时没有更新，还是 f_{i-1,j-v_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]);

二维 01 背包

二维 01 背包照样是有 n 件物品，但每件物品有一个体积 z_i 和一个质量 c_i ，要求的答案是在体积不超过 x 且质量不超过 y 时，可以达到的最大价值。

思路和 01 背包一样，f_{i,j,k} 就是用前 i 个物品，用 j 个体积，k 个质量能达到的最大价值。

那么就要开三重循环了，分别枚举前 i 件物品，j 个体积，k 个质量。

转移方程也和 01 背包同理，f_{i,j,k}=f_{i-1,j-z_i,k-c_i}，理解了上面 01 背包的应该很容易理解吧？

那么代码大概长这样子：

for(int i=1; i<=n; i++)
    for(int j=1; j<=x; j++)
        for(int k=1; k<=y; k++)
            if(j>=z[i] && k>=c[i]) f[i][j][k]=max(f[i-1][j][k],f[i-1][j-z[i]][k-c[i]]+w[i]);
            else f[i][j][k]=f[i-1][j][k];

三维数组，显然在某些情况下会炸掉内存，还是考虑和 01 背包一样的滚动数组优化。

直接去掉第一维是这样子的：

for(int i=1; i<=n; i++)
    for(int j=1; j<=x; j++)
        for(int k=1; k<=y; k++)
            if(j>=z[i] && k>=c[i]) f[j][k]=max(f[j][k],f[j-z[i]][k-c[i]]+w[i]);
            else f[j][k]=f[j][k];

还是老样子，else 里的东西不需要，j 和 k 可以直接分别从 z_i 和 c_i 开始循环。

for(int i=1; i<=n; i++)
    for(int j=z[i]; j<=x; j++)
        for(int k=c[i]; k<=y; k++)
            f[j][k]=max(f[j][k],f[j-z[i]][k-c[i]]+w[i]);

同上，需要倒着跑。

for(int i=1; i<=n; i++)
    for(int j=x; j>=z[i]; j--)
        for(int k=y; k>=c[i]; k--)
            f[j][k]=max(f[j][k],f[j-z[i]][k-c[i]]+w[i]);

P1507 NASA的食物计划

题目大意

有 n 个食品，每个食品有相应的体积 z_i，质量 c_i，价值为 w_i，给定体积最大值 x，质量最大值 y，求最大价值。

代码

#include <iostream>
using namespace std;
const int N=5e2+5;
int n,x,y;
int z[N],c[N],w[N];
int f[N][N];

int main(){
    scanf("%d%d%d",&x,&y,&n);
    for(int i=1; i<=n; i++) scanf("%d%d%d",&z[i],&c[i],&w[i]);
    for(int i=1; i<=n; i++)
        for(int j=x; j>=z[i]; j--)
            for(int k=y; k>=c[i]; k--)
                f[j][k]=max(f[j][k],f[j-z[i]][k-c[i]]+w[i]);
    printf("%d\n",f[x][y]);
    return 0;
}

推荐习题

• P2871 [USACO07DEC]Charm Bracelet S 板子，不用多说。
• P1049 [NOIP2001 普及组] 装箱问题 01 背包稍微变化。
• P1060 [NOIP2006 普及组] 开心的金明 同上。
• P1164 小A点菜 同上。
• P1926 小书童——刷题大军 变化得比上面几道要大一点。
• P1910 L国的战斗之间谍 二维 01 背包板子。
• P1877 [HAOI2012]音量调节 二维 01 背包变形。

欸嘿，01 背包讲完了。然后是完全背包。

完全背包

完全背包与 01 背包不同的点就在于每种物品可以选择无限个。

但是，代码和 01 背包的差别特别小，唯一的区别就在状态转移方程上：

• 01 背包：f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}。
• 完全背包：f_{i,j}=\max\{f_{i-1,j},f_{i,j-v_i}+w_i\}。

要是理解了 01 背包，那么完全背包的代码是很好背的，但关键是为什么就少一个 -1。

那么我们来看一下相当于暴力的完全背包转移方程，也就是判断选多少个第 i 件物品才是最优解。

于是这题就可以愉快地做完啦。

代码

#include <iostream>
using namespace std;
const int N=1e3+5;
int n,V,g,gp; // n 物品个数，V 最大重量，g 总组数，gp 输入的组数
int v[N],w[N]; // 每个物品的重量及价值
int m[N],r[N][N]; // m[i] 第 i 组物品总数，r[i][j] 第 i 组第 j 个物品的编号
int f[N]; // dp 数组

int main(){
    scanf("%d%d",&V,&n);
    for(int i=1; i<=n; i++){
        scanf("%d%d%d",&v[i],&w[i],&gp);
        g=max(g,gp);
        m[gp]++;
        r[gp][m[gp]]=i;
    }
    for(int i=1; i<=g; i++) // g 个组
        for(int j=V; j>=0; j--) // 重量
            for(int k=1; k<=m[i]; k++){ // 枚举第 i 组中的物品
                if(j<v[r[i][k]]) continue; // 这种情况不需要且不能更新
                f[j]=max(f[j],f[j-v[r[i][k]]]+w[r[i][k]]);
            }
    printf("%d\n",f[V]);
    return 0;
}

推荐习题

• P5322 [BJOI2019] 排兵布阵

对，就这，没题了...

混合背包

差不多就是一个多重背包。

有 n 种物品，每种物品可能有 1，k_i，\infty 个，每个物品有一个重量 v_i 和一个价值 w_i，现给定背包最大承重 V，求最大价值。

对于 \infty 个，取 \lfloor\dfrac{V}{v_i}\rfloor 即可。因为你就算有再多个物品可以取，总重量也不能有 V 大吧？

我们确定了数量就可以用多重背包的方式做了。

P1833 樱花

题目大意

有 n 棵樱花树，每棵有美学值 w_i 和观赏消耗的时间 v_i，可以赏 k_i 次。若 k_i 为 0，表示可以赏无限次。

现给定可以用来赏花的时间区间（开始时间与结束时间），请求出最大的美学值。

思路

还是和多重背包风格一样，就算预处理复杂一点也一定要让后面完全等于 01 背包！

没什么好讲的，只是可以说说时间计算部分。

设开始时间为 h1:m1，结束时间为 h2:m2。

首先我们不考虑任何因素，计算分钟数是这样的：V=(h2-h1) \times 60+m2-m1。这个应该很好理解。

但有可能 m2 \leq m1，这时候就要让 m2 变大了。

怎么个变大法呢？自然是将一个小时的 60 分钟加上去了！注意这样操作后 h2 需要减一。

代码

#include <iostream>
using namespace std;
const int N=1e6+5;
int h1,h2,m1,m2;
int n,V,t,k;
int a[N],b[N];
int v[N],w[N];
int f[N];

int main(){
    scanf("%d:%d%d:%d%d",&h1,&m1,&h2,&m2,&t);
    if(m2>m1) m2+=60,h2--;
    V=(h2-h1)*60+m2-m1; // 计算时间
    for(int i=1; i<=t; i++){
        scanf("%d%d%d",&a[i],&b[i],&k);
        if(!k) k=V/a[i]; // 为 0 时有无限个
        for(int j=1; j<=k; j<<=1){ // 和多重背包一样
            n++;
            v[n]=a[i]*j;
            w[n]=b[i]*j;
            k-=j;
        }
        if(k){
            n++;
            v[n]=a[i]*k;
            w[n]=b[i]*k;
        }
    }
    for(int i=1; i<=n; i++) // 01 背包板子
        for(int j=V; j>=v[i]; j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    printf("%d\n",f[V]);
    return 0;
}

推荐习题

• P1782 旅行商的背包

又没了...