概念

01背包之所以叫“01”背包，就是它需要选择是否将当前这样物品装入背包。$0$ 代表不装，$1$ 代表装。

一、板子题和强化

题目描述

有一个最多能装 $m$ 千克的背包，有 $n$ 块魔法石，它们的重量分别是$W_1,W_2,…,W_n$ ，它们的价值分别是 $C_1,C_2,…,C_n$。若每种魔法石只有一件，问能装入的最大总价值。

输入格式

第一行为两个整数 $m$ 和 $n$，以下 $n$ 行中，每行两个整数 $W_i,C_i$，分别代表第 $i$ 件物品的重量和价值。

输出格式

输出一个整数，即最大价值。

样例输入

1
2
3
4
8 3
2 3
5 4
5 5

样例输出

1
8

1.板子

$1\le m \le 30,1\le n\le 15$.

首先还是分析问题：每个东西都可以选择选或不选。我们假设正在抉择第 $i$ 个物品，如果选的话，我们需要付出的代价就是占据一部分的背包容量。可见有两个因素在影响dp数组的值：$i$ 和背包容量 $m$。

因此可以定义dp数组的意义为：

$dp_{i,j}$ 代表在前 $i$ 件物品中做选择，背包容量为 $j$ 时能获得的最大价值。

好，继续分析，每次对于第 $i$ 个物体的抉择，无非是选和不选的两种情况。

如果选的话，那么在选择前 $i-1$ 个物体的时候，可以使用的背包容量就需要减少 $w_i$，但是所获得的价值就可以加上 $c_i$。

如果不选，那就和选择前 $i-1$ 个物品的最优情况是一样的。

可得出动态转移方程：

Code

把动态转移方程套到程序里面就可以了，注意循环两层从小到大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,m,w[20],c[20],dp[20][35];
int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&w[i],&c[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(w[i]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
        }
    }
    printf("%d",dp[n][m]);
    return 0;
}

2.压缩空间

$1\le m \le 3\times 10^6,1\le n\le 100$，空限变得极度 duliu。

考虑优化空间复杂度。

上述程序的 $dp$ 数组为二维数组，但是大家注意到动态转移方程时只需要用到 $dp_{i-1,?}$ 的值。

这也就意味着我们可以使用滚动数组优化空间复杂度。（不过时间复杂度就没法变了……）

需要注意的是，因为问号处的值必定小于 $j$，所以我们 $j$ 这一维需要倒着枚举，不然在利用前面的值的时候就会错利用为 $dp_{i,?}$ 而非 $dp_{i-1,?}$ 的值了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#define max(a,b) (a)>(b)?(a):(b)
int m,n,dp[35],w[20],c[20];
int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&w[i],&c[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    printf("%d",dp[m]);
    return 0;
}

3.如果有其它的限制条件……

$1\le n\le 100$

$1\le W_i,m\le 10^9$

$1\le C_i\le 10^7$

对于每个 $i=2,3,…,n$，满足 $W_1\le W_i\le W_1+3$

如果按照背包的板子做，那么一定会 TLE 和 MLE。那如何优化呢？

我们注意到数据范围里有一句十分特殊的话：

对于每个 $i=2,3,…,n$，满足 $W_1\le W_i\le W_1+3$

那么我们完全可以把每个物品的重量以 $W_1$ 为基准，转化为一个不超过 $3$ 的数。这么可以极大地优化空间复杂度。

用 $h$ 代表 $W_1$ 的真实数字。

但是这样的话，我们就无法得知我们现在装的东西到底有没有超过背包的容量，因为我们并不知道我们选了多少个东西。所以 $dp$ 数组还需要开一维代表选择物品的个数。

所以 $dp_{i,j,k}$ 代表在前 $i$ 个物品中选择 $k$ 个物品，背包容量为 $j$ 时的最大价值。

还需要注意一下循环的范围：

  • $i:1\sim n$

（这个不需要解释了吧……）

  • $j:0\sim 3\times i$

（因为物品的重量被处理过，当原来的 $W_i=W_1$ 时这个物品的重量为 $0$。所以最小的背包容量有可能是 $0$。物品最大的重量不超过 $3$，有 $i$ 个物品，所以最大可能容量为 $3\times i$。）

  • $k:1\sim i$

（选择的物品数量不能超过总数。因为后面求答案 $ans$ 的初始值就为 $0$ 已经包括了一个都不选的情况，所以不需要考虑不选物品的情况。）

最后求答案的时候需要枚举 $dp_{n,i,j}$，注意只有 $i+j\times h\le m$ 时背包才不超限，可以更新答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#define max(a,b) (a)>(b)?(a):(b) //卡常小技巧：用这个比库函数要快一些
#define ll long long
ll n,m,ans,h,w[105],v[105],dp[105][305][105];
int main(){
    scanf("%lld %lld",&n,&m);
    scanf("%lld %lld",&h,&v[1]); //h 代表 W1 的的重量
    for(int i=2;i<=n;i++){
        scanf("%lld %lld",&w[i],&v[i]);
        w[i]-=h; //以 W1 为基准转化每一件物品的重量
    }
    for(int i=1;i<=n;i++){
        for(int k=1;k<=i;k++){ //选择的物品数量不能大于总数量
            for(int j=0;j<=3*i;j++){ //3*i 为被允许的最大容量
                if(j<w[i])
                    dp[i][j][k]=dp[i-1][j][k];
                else
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-1]+v[i]);
            }
        }
    }
    //在合法的范围内寻找最大值
    for(int i=0;i<=3*n;i++){
        for(int j=0;j<=n;j++){
            if(i+j*h<=m)
                ans=max(ans,dp[n][i][j]);
        }
    }
    printf("%lld",ans);
    return 0;
}

二、比较简单的应用

一些适合背包初学者体会的题目~

例2-1.采药

题目链接

非常板的一道题，把板子搬过来即可。

例2-2.装箱问题

题目链接

也是板子题，因为没有价值，而要求剩余空间最小，那么就是让重量尽量大。所以我们可以把重量当作价值，在不超过容量的前提下把剩余空间尽量变小。

Code （非滚动写法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int m,n,w[35],dp[35][20005];
int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(w[i]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
        }
    }
    printf("%d",m-dp[n][m]); //求的是剩余空间所以需要做减法
    return 0;
}

例2-3.数字分组1

题目链接

简化题意：给出若干个数字，把这些数字分为两组使两组数字的和的差距尽量小。

因为要让两组尽量接近，即接近 $\big (\sum\limits_{i=1}^{n}w_i\big ) ÷2$，所以我们规定一个背包的大小为这个数，然后让一组的重量尽量靠近这个值（也就是例 $2-2$，顺便展示一下例 $2-2$ 的滚动数组写法），再分别输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int m,sum,n,w[35],dp[300005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        m+=w[i];
        sum+=w[i];
    }
    m=(m+1)/2; //为了以防万一向上取整也是可以的
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
        }
    }
    int k=sum-dp[m];
    printf("%d",abs(k-dp[m]));
    return 0;
}

三、01背包问题输出方案

DP 算法输出方案的思想都是差不多的，即，开一个 $pre$ 数组记录每一步的决策，然后输出的时候根据 $pre$ 数组倒推回去。

我们来看一些例题。

例3-1.01背包输出方案

题目即让一个普通的01背包输出方案——输出要选择的物品编号。

那么，在每次求最大值的时候，我们就不能用 $\max$ 了，而是打一个条件选择，如果能更新 $dp_j$ 的值，那么我们就更新 $dp_j$，而且把 $pre_{i,j}$ 设为 $1$，代表在背包容量为 $j$ 的情况下要选择 $i$ 物品。

最后的输出可以用递归，也可以用循环。这里本人比较偏向于打递归（倒着推，代码较为简短），大家可以结合注释好好理解一下这个递归的输出函数：

1
2
3
4
5
6
7
8
void print(int x,int y){ //x代表物品的编号，y代表背包此时的容量
    if(!x) return; //物品已经枚举完
    if(pre[x][y]){ //要选这个物品
        print(x-1,y-w[x]); //往前推，背包的容量需要减少这个物品的重量
        printf("%d ",x); //输出（因为要正着输出但是我们是倒着推的，所以在运行完了上面的递归函数后才输出）
    }else print(x-1,y); //不选的话就不用减少背包容量了
    return;//华丽结束~
}

有时候，题目会要求我们输出使用背包容量最小时的方案，我们在调用函数的时候 $y$ 参数就不可以直接填 $m$，而是进行一次循环，从小往大枚举，如果 $dp_i=dp_m$（最优解），就把这个 $i$ 值代入函数的 $y$ 参数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#define max(a,b) (a)>(b)?(a):(b)
int m,n,dp[35],w[20],c[20],pre[20][35];
void print(int x,int y){
    if(!x) return;
    if(pre[x][y]){
        print(x-1,y-w[x]);
        printf("%d ",x);
    }else print(x-1,y);
    return;
}
int main(){
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&w[i],&c[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            //dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
            if(dp[j-w[i]]+c[i]>dp[j]){
                dp[j]=dp[j-w[i]]+c[i];
                pre[i][j]=1;
            }
        }
    }
    printf("%d\n",dp[m]);
    int t=0;
    for(int i=1;i<=m;i++){
        if(dp[i]==dp[m]){
            t=i;
            break;
        }
    }
    print(n,t);
    return 0;
}

例3-2.CD

题目链接

和上述题目差不多，有多组输入，但是输出要求要输出和。

不过因为和是在最后输出，所以我们可以在递归函数的过程中统计选择了多少个 CD，代码实现很简单。

再说一句：如果是要求在输出方案之前输出和，那么我们就需要再准备一个数组，先用此函数统计和（但是把输出语句改为把答案存到数组里的语句），输出 $sum$，然后输出数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
int m,n,dp[10005],a[105],pre[105][10005],sum;
void print(int x,int y){
    bool flag=0;
    if(!x)
        return;
    if(pre[x][y]){
        flag=1;
        print(x-1,y-a[x]);
    }else
        print(x-1,y);
    if(flag){
        printf("%d ",a[x]);
        sum+=a[x];
    }
    return;
}
int main(){
    while(scanf("%d %d",&m,&n)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>=a[i];j--){
                if(dp[j-a[i]]+a[i]>m)
                    continue;
                if(dp[j-a[i]]+a[i]>=dp[j]){
                    dp[j]=dp[j-a[i]]+a[i];
                    pre[i][j]=1;
                }
            }
        }
        print(n,m);
        printf("sum:%d\n",sum);
        sum=0;
    }
    return 0;
}

四、需要排序的01背包问题

到这个阶段，背包问题就开始有难度了。

背包问题本身是不需要排序的。需要排序的背包问题就是说在做某个决策的时候，一些参数（如背包容量等）会发生变化，为了得到最优解，我们需要对背包的物品进行排序。

一般来说，排序的过程涉及到贪心的思想，我们可以使用假设的方法。这种方法会在下面的题解中详细介绍。

还是来看一些例题来加强理解吧。

例4-1.骄傲的商人

题目链接

题意简述：有一些商人，每个商人只卖一件商品，价格是 $P_i$，但是如果你的钱少于 $Q_i$，你就不能买这个东西。你评估了每一件商品的价值 $V_i$。而且你只有 $M$ 单位的钱，那么你能得到的最大价值是多少?

其实这道题是非常简单的，就是十分普通的01背包板子，只需要在前面加一个判断总钱数是否大于 $Q_i$ 的程序就好啦~

结果你交上去会发现错了（（

为什么呢？疑惑(っ´Ι`)っ？？

原因是这样的：

因为每一次购买物品都需要耗钱买，那么有些本来可以买的东西因为枚举较为靠后就没有买到。

所以呢，我们需要对每一件商品进行排序，让每个让我拿到最优解的东西都可以买到。

那么怎么排序呢？这时候就需要假设法（名字我自己取的）来分析了！

使用结构体存储每件商品的信息，然后假设我们要买两件商品 $x$ 和 $y$，而且你的钱 $M$ 大于两个商品耗费的钱之和。

假设如果你先买 $x$ 商品比先买 $y$ 商品方案更优。

那么就只有一种情况：买了 $x$ 后可以继续买 $y$，但是买了 $y$ 之后就不可以买 $x$ 了。

$x\ \ \ \ x.p\ \ \ x.q\ \ \ x.v$
$y\ \ \ \ y.p\ \ \ y.q\ \ \ y.v$

（把所有条件都列在草稿纸上以便分析，一定要养成好习惯哦！）

所以可以得出：

$
\begin{cases}
M-x.p\ge y.q\cdots(1)\\
M-y.p<x.q\cdots(2)
\end{cases}
$

整理一下式子可以得到：

$
\begin{cases}
M-x.p\ge y.q\cdots(1)\\
y.p-M>-x.q\cdots(2)
\end{cases}
$

（右边负号别漏了）

$(1)+(2)$ 可得：

$y.p-x.p>y.q-x.q$

移项变号：

$x.q-x.p<y.q-y.p$

就得出了最后排序的式子。

使用的时候，$x$（放在前面更优的物品）放在 cmp 传参的前面，$y$ 放在cmp 传参的后面，直接 return 推出来的式子即可。当然，你愿意保险一点像我一样写条件选择也没问题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,dp[5005];
struct node{
    int p,q,v;
}a[505];
bool cmp(node x,node y){
    if(x.q-x.p>=y.q-y.p)
        return false;
    return true;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&a[i].p,&a[i].q,&a[i].v);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i].q;j--){
            dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);
        }
    }
    printf("%d",dp[m]);
    return 0;
}

例4-2.烹调方案

题目链接

很明显这道题是需要排序的，因为每一道菜的美味指数与时间有关，所以需要排序安排做每个食物的顺序。不过现在这并不是我们的重点。

问题是：背包容量是啥，重量是啥，价值又是啥呢？

题目中只规定了一个时间，所以重量限制就是做菜的时间；需要获得的是最大的美味指数，所以价值就是每道菜的美味指数。（我说了先暂时不管时间对食物价值的损耗，只是推状态转移方程而已啦！）

外层循环 $i$：枚举每个食物。

内层循环 $j$：枚举过了多少时间。

特别注意！ 在背包问题中，需要注意你的内层循环这个数值到底代表的是最多这么多限制还是刚好这么多限制，这道题因为不需要用到非常精准的时间分钟数所以是最多的限制，$dp$ 数组不需要初始化极小值，所有数为 $0$ 即可。

每个食物的重量：$c_i$

每个食物的价值：$a_i-j\times b_i$

照着板子打上去就可以了。现在是考虑排序的时间~

还是假设要做两个食物 $x$ 和 $y$，先做 $x$ 比先做 $y$ 获得的美味指数多。为了方便，时间从 $0$ 开始且不考虑食物美味指数小于等于 $0$ 的情况。

$x\ \ \ \ x.a\ \ \ x.b\ \ \ x.c$
$y\ \ \ \ y.a\ \ \ y.b\ \ \ y.c$

先做 $x$ 的美味指数：$x.a+y.a-y.b\times x.c$

先做 $y$ 的美味指数：$y.a+x.a-x.b\times y.c$

由假设得出结论：

$x.a+y.a-y.b\times x.c>y.a+x.a-x.b\times y.c$

整理得：

$-y.b\times x.c>-x.b\times y.c$

去掉负号：

$y.b\times x.c<x.b\times y.c$

OK，式子推出来了。还是用结构体存储排序打代码。

代码记得开 long long。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll T,n,ans,dp[100005];
struct food{
    ll a,b,c;
}w[55];
bool cmp(food x,food y){
    if(x.c*y.b>=x.b*y.c)
        return false;
    return true;
}
int main(){
    scanf("%lld %lld",&T,&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i].a);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i].b);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i].c);
    }
    sort(w+1,w+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=T;j>=w[i].c;j--){
            dp[j]=max(dp[j],dp[j-w[i].c]+w[i].a-w[i].b*j);
        }
    }
    for(int i=1;i<=T;i++){
        ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
    return 0;
}

说句闲话

其实上面两道题代表得是本人认为对于需要排序得背包问题的两大类：

骄傲的商人 $→$ 不同的排序方式，一些情况成立，另一些则无法成立。每种情况只要成立创造的价值都是相同的。

列出来的式子通常是 $2$ 个及以上，需要合并，较为麻烦。

烹饪方案 $→$ 不同的排序方式，所有情况都成立，可是创造的价值不同。

通常只会列出一个式子进行推到，相对比较容易。

当然肯定会有两者的结合题目，只不过本人暂时未遇到就先不说了。

五、01背包进阶

到了这个阶段，01背包就已经不是单纯的背包问题了，其本质上是每进行一个操作参数的变化。具体表现为：“背包的容量”和物品的“重量”、“价值”不是很好找，而且很有可能根据某些操作变化。

我们来看一些例题。

例5-1.Course Selection System

题目链接

题意简述：有 $n$ 个物品，第 $i$ 个物品都有两个权值 $H_i$ 和 $C_i$。现在选出若干个物品（可以不选）$x_1,x_2,\ldots ,x_m$ 使得 $ans$ 最大。

$ans=\big(\sum\limits_{i=1}^{m}H_{x_i}\big)^2-\big(\sum\limits_{i=1}^{m}H_{x_i}\big)\times \big(\sum\limits_{i=1}^{m}C_{x_i}\big)-\big(\sum\limits_{i=1}^{m}C_{x_i}\big)^2$

这道题乍一看没有什么思路，那我们就需要对这个式子进行处理。

首先，根据观察可得：这道题中 $H_i$ 主要是让答案更大，$C_i$ 是让答案更小。可以说，$C_i$ 是答案的限制。所以，我们可以把 $C_i$ 作为背包的容量和每一件物品的重量。不难看出，背包的最大容量应该是 $\sum\limits_{i=1}^{n}C_i$。

那么相应地，$H_i$ 就可以作为物品的价值，所以存在 $dp$ 数组里面的值就是固定 $C_i$ 下的最大 $H_i$ 之和。

在进行一次 01 背包之后，你不要以为就万事大吉了！因为不一定 $C_i$ 大的 $ans$ 值就是最优解，所以我们需要遍历 $dp$ 数组，每次在计算答案的时候按照题目要求的格式计算即可。具体看代码理解。

最后注意开 long long，注意多组数据和每次的初始化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<cstring>
#define max(a,b) (a)>(b)?(a):(b)
#define ll long long
ll t,n,ans,sum,h[505],c[505],dp[50005];
int main(){
    scanf("%lld",&t);
    while(t--){
        memset(dp,0,sizeof(dp)); //多组数据要初始化
        ans=0,sum=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld %lld",&h[i],&c[i]);
            sum+=c[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=c[i];j--){
                dp[j]=max(dp[j],dp[j-c[i]]+h[i]);
            }
        }
        for(ll i=1;i<=sum;i++){ //i遍历的是 Ci 的值，dp 数组里的值代表 Hi
            ans=max(ans,dp[i]*dp[i]-dp[i]*i-i*i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

例5-2.Dima and Salad

题目链接

本题解已审核通过，欢迎大家资瓷~link

首先假设我们选了 $m$ 个水果。已知：

转换式子后可得：

再次转换：

可以写成：

所以我们可以让第 $i$ 个水果的重量为 $a_i-b_i\times k$，最后只要让重量总和等于 $0$ 就算满足条件啦。

此时我们需要注意初始值：因为按照上面这么分析，水果的重量和完全有可能是负数。这个时候看到数据范围：

$1\le n\le 100,1\le k\le 10,1\le a_i,b_i\le 100$

最小极限情况：$n=100,k=10,a_i=1,b_i=100$

那么重量总和就为：

$100\times (1-100\times 10)\approx -100000$

所以 $dp$ 数组中，每一个数字都需要加上 $100000$ 以保证不越界。我们可以定义一个常量 $p=100000$，写代码更加简洁，不过不写也是可以的。

接着我们计算最大极限情况：$n=100,k=1,a_i=100,b_i=1$

那么重量总和就为：

$100\times (100-1\times 1)\approx 10000$

所以 $dp$ 数组需要开 $110000+5$，这也是最大有可能出现的背包容量。

最后要注意：因为重量有正有负，所以我们不知道循环是从小到大还是从大到小。所以我没有打滚动，如果要打滚动，需要注意判断重量的正负之后判断循环的顺序。

打代码要注意细节，我错了很多次才对。

（PS：我打代码的时候觉得 $a_i-b_i\times k$ 看着不爽，就改成了 $b_i\times k-a_i$，这样在分析极限值的时候有变化，需要注意。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#define max(a,b) (a)>(b)?(a):(b)
int n,k,a[105],b[105],m[105],dp[105][110005];
int main(){
    memset(dp,-1,sizeof(dp));
    dp[0][10000]=0; //最后答案的位置是0
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        m[i]=k*b[i]-a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=110000;j>=0;j--){
            if(j-m[i]<=110000&&j-m[i]>=0){ //不能越界，越了界后面就没有回来的可能性了，直接跳过此循环
                if(dp[i-1][j-m[i]]==-1)
                    dp[i][j]=dp[i-1][j]; //不可能
                else
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-m[i]]+a[i]);
            }
        }
    }
    if(dp[n][10000])
        printf("%d",dp[n][10000]);
    else
        printf("-1");
    return 0;
}

例5-3.多米诺骨牌

题目链接

emmm 这也许是一道转化比较复杂的01背包问题了。

首先对于每个骨牌，都有转与不转两种抉择，相当于01背包里的“选和不选”。

其次，要求的是“上下分别之和的差得绝对值”尽量小。为了方便，我们把这个差记为上面减下面的差。假如说我们把第 $i$ 个骨牌的上面点数记为 $a_i$，下面的点数记为 $b_i$，那么每旋转一个骨牌，那么上下和的差就会减少 $2\times (a_i-b_i)$，这个 $2$ 可以约掉。我们可以把这个东西记为第 $i$ 个骨牌旋转后的重量。

每个骨牌的价值是 $1$，我们要让价值最小。

但是这道题和上一道题有相同的地方，就是万恶的负重量！于是我们又要分析数据的极限值了 qwq。

分析过程省略，反正最后出来是 $-5000\sim 5000$。

所以 $dp$ 数组关于容量的那个下标需要统一加上 $5000$。

另外还有就是与上面一样，因为重量有正有负，所以打滚动需要注意循环的顺序。

求答案：那如何让在产生最优的重量时求得最小的价值呢？我们可以把 $dp$ 数组先全部初始化为极大值，只把 $dp_{0,5000}$ 定义为 $0$，在求解答案的过程中，从小到大枚举背包占的容量，只要有一个数字不是极大值，就可以直接输出。不过因为让求的是差的绝对值的最小值，所以枚举的时候，两边（重量为正和负）都需要看一下。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int ans,n,a[1005],b[1005],c[1005],dp[1005][10005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        c[i]=a[i]-b[i];
    }
    memset(dp,127,sizeof(dp));
    dp[0][5000]=0;
    for(int i=1;i<=n;i++){
        for(int j=10000;j>=c[i];j--){
            dp[i][j]=min(dp[i-1][j-c[i]],dp[i-1][j+c[i]]+1);
        }
    }
    for(int i=0;i<=5000;i++){
        int ans=min(dp[n][5000-i],dp[n][5000+i]);
        if(ans!=2139062143){
            printf("%d",ans);
            return 0;
        }
    }
    return 0;
}

例5-4.夏季特惠

题目链接

题意简述：有 $n$ 个商品，第 $i$ 个商品原价为 $a_i$，打折后的价格为 $b_i$，买到这个东西你的快乐值会增加 $w_i$。你的钱数是无限的，预算为 $m$ 元，只要花的钱不超过 $m$ 或者获得的总优惠金额不低于超过预算的总金额，那么你就不会觉得吃亏。现在请你在感觉不吃亏的前提下获得最多的快乐值。

这道题很明显背包是会根据买的东西变化的。具体表现为：每买一样东西，背包会先减去 $b_i$，再加上 $a_i-b_i$ （获得优惠的金额）。

那么易证只要买的东西价格满足 $a_i\ge 2\times b_i$，那背包可用的容量不仅不会减少，而且可能会增加。

所以满足上述条件的商品是一定要买的。

接着考虑剩下的物品。上面已经分析，在买了一个物品后，背包的可用容量 $H$ 就会变成 $H-2\times b_i+a_i$。所以商品的重量可以规定为 $2\times b_i-a_i$。而因为剩下的商品不满足上述条件，所以买了背包的容量是一定会减小的，即剩下的商品重量不会为负数。

商品的价值是 $w_i$，这个很明显。

代码实现很简单，哦，对了，记得开 long long。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,tot,ans,a[505],b[505],h[505],c[505],w[505],dp[5000005];
int main(){
    scanf("%lld %lld",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld %lld",&a[i],&b[i],&h[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]>=2*b[i]){
            x+=a[i]-2*b[i];
            ans+=h[i];
        }else{
            w[++tot]=2*b[i]-a[i];
            c[tot]=h[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=x;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    printf("%lld",ans+dp[x]);
    return 0;
}

总结

01背包这个算法有非常多的变化形式，唯有多看题、刷题、总结题型才能真正掌握。同时它还是后面其它背包问题的基础，所以学好 01 背包是一个十分重要的版块。

终于写完了！完结撒花！❀╰(*°▽°*)╯❀

Markdown 竟然写了 $900^+$ 行，创历史新高啊 qwq。