Home 背包问题
Post
Cancel

背包问题

01背包问题

特点: 一个物品只能选择一次.

1
2
3
4
5
for(int i=1;i<=N;++i){
    for(int j=V;j>=w[i];++j){
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

模板题 1: AcWing 423 采药

Link

每个物品只有 1 个, 且具有价值和体积两个属性.

体积就是消耗, 价值就是最后要求的结果, 通常求最大值.

递推公式:

1
2
3
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
//优化掉一维
dp[j]=max(dp[j],dp[j-w[i]]+v[i])

模版代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int t,m;
int w[110],v[110],dp[1010];
int main() {
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&w[i],&v[i]);
    for(int i=1;i<=m;++i)
        for(int j=t;j>=w[i];--j) //倒着输出是为了保证dp[j-w[i]]是i-1那一层的(当前是第i层)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    printf("%d\n",dp[t]);
    return 0;
}

模板题 2: AcWing 1024 装箱问题

Link

每个物品只有 1 个, 只具有一个属性, 但是这个属性可以同时作为价值和体积.

并且在满足 j>=minv*2 后恒有 dp[j-w[i]]==j-w[i] 成立, 其中 minv 是最小的 w[i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int v,n;
int w[35],dp[20010];
int main() {
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;++i)
        for(int j=v;j>=w[i];--j)
            dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
    printf("%d\n",v-dp[v]);
    return 0;
}

模板题 3: PAT 1068 Find More Coins

Link

在 01 背包模版题 2 的基础上增加了路径回溯.

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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m;
int a[10010],dp[110];
bool choose[10010][110];
vector<int>ans;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n,greater<int>());
    for(int i=1;i<=n;++i){
        for(int j=m;j>=a[i];--j)
            if(dp[j]<=dp[j-a[i]]+a[i]){
                dp[j]=dp[j-a[i]]+a[i];
                choose[i][j]=true;
            }
    }
    if(dp[m]!=m) printf("No Solution\n");
    else{
        int cur=m,k=n;
        while(cur>0){
            if(choose[k][cur]){
                ans.push_back(a[k]);
                cur-=a[k];
            }
            k--;
        }
        for(int i=0;i<ans.size();++i){
            if(i!=0) printf(" ");
            printf("%d",ans[i]);
        }
    }
    return 0;
}

模版题 4: AcWing 1022 宠物小精灵之收服

Link

这道题是经典的 二维费用 01 背包问题. 精灵球数量是第一费用, 皮卡丘受到的伤害是第二费用, 最后要求出最多的物品数量.

“主要目标是收服尽可能多的野生小精灵, 如果可以收服的小精灵数量一样 (first), 小智希望皮卡丘受到的伤害越小 (second)”.

想法其实很简单, 就是在之前一维费用的基础上增加一个维度表示第二个要考虑的费用. 三个维度再加上滚动数组优化, 只需要两个维度即可.

在一维费用的 01 背包问题中, dp[i][j] 表示前 i 个物品中费用不超过 j 的最大值. 那么此时就变成了: dp[i][j][k] 表示前 i 个物品中第一维费用不超过 j、第二维费用不超过 k 的最大值.

  • 不选择第 i 个物品, dp[i][j][k]=dp[i-1][j][k];
  • 选择第 i 个物品, dp[i][j][k]=dp[i-1][j-w1[i]][k-w2[i]]+v[i].

这道题有个坑. 题目中有这样一句话: “当皮卡丘的体力小于等于 0 时, 小智就必须结束狩猎 (因为他需要给皮卡丘疗伤), 而使得皮卡丘体力小于等于 0 的野生小精灵也不会被小智收服”. 因此不能让皮卡丘的体力等于 0! 如果某只精灵让皮卡丘的体力等于 0 了, 那么这只精灵就不会被捕捉. 所以皮卡丘剩余体力的最小值是 1 而不是 0, 即能够消耗的体力是 m-1 而不是 m. 在遍历当前最大可消耗的体力值的时候, 也应该从 m-1 开始.

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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,k;
int v1[1010],v2[510],dp[1010][510];
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i)
        scanf("%d%d",&v1[i],&v2[i]);
    for(int s=1;s<=k;++s)
        for(int i=n;i>=v1[s];--i)
            for(int j=m-1;j>=v2[s];--j)
                dp[i][j]=max(dp[i][j],dp[i-v1[s]][j-v2[s]]+1);
    printf("%d ",dp[n][m-1]);
    //找到满足最大价值的所有状态中第二维费用消耗最少的
    for(int i=0;i<m;++i)
        if(dp[n][i]==dp[n][m-1]){
            printf("%d\n",m-i);
            break;
        }
    return 0;
}

另外, 在背包问题中,体积 w 与价值 v 是可以互逆的.

可以将 f[i] 表示为体积为 i 能装的最大价值, 也可以将 f[i] 表示为价值为 i 所需的最小体积.

以上两者等价, 因此我们只需要选择范围较小的那维作为体积就可以了. 而这直接影响到时间和空间复杂度.

完全背包

特点: 一个物品可以选择多次.

1
2
3
4
5
6
7
for(int i=1;i<=N;++i){
    for(int j=1;j<=V;++j){
        dp[i][j]=dp[i-1][j];
        if(j>=w[i])
            dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
    }
}

为什么是这样?

先来看看几种不够好的方法:

转化成 01 背包:

既然一件物品可以选择多次, 那么最直观的想法其实是转化成 01 背包问题. 虽然一件物品有无限个, 但是限于背包容量 V, 我们其实最多只能取 V/w[i] 个物品 i. 因此, 在 01 背包的两层循环上再加一层 for(int k=0;k<=j/w[i];++k) 就可以了:

1
2
3
4
5
6
7
8
//w[i]是物品体积,v[i]是物品价值
for(int i=1;i<=N;++i){
    for(int j=1;j<=V;++j){
        for(int k=0;k<=j/w[i];++k){
            dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
        }
    }
}

这样做有什么缺点?

复杂度! 时间复杂度为 $O(NV\sum_j{\dfrac{j}{w[i]}})$, 空间复杂度为 $O(NV)$ .

简单优化一下:

若两件物品满足 w[i]<=w[j] && v[i]>=v[j], 则将第 j 种物品直接筛掉, 因为第 i 种物品比第 j 种物品物美价廉 (价值大体积小), 用 i 替换 j 能得到不会更差的方案.

这个筛选过程如下: 先找出体积大于背包的物品直接筛掉, 复杂度 $O(N)$ . 利用计数排序思想对剩下的物品体积进行排序, 同时筛选出相同体积中价值最大的物品留下, 其余的都筛掉, 复杂度 $O(V)$ . 整个过程的时间复杂度为 $O(N+V)$ . 当然, 这两个过程中也可能一种物品都筛不掉.

二进制优化:

每个正整数都可以用 2 的幂之和来表示 (其实就是因为每个数都有其二进制表示, 可以表示为每一位乘以其位权).

假设第 i 种物品需要取 x (x 是个十进制数, 表示成二进制就有 m 位) 个, 且 $x=a_0\cdot 2^0+a_1\cdot 2^1+\dots +a_{m-1}\cdot 2^{m-1}$. 那么, 我们要取 x 个物品 i, 本质上是要取 $a_0$ 次 $2^0$ 个物品 i, $a_1$ 次 $2^1$ 个物品 i, $a_2$ 次 $2^2$ 个物品 i, …, $a_{m-1}$ 次 $2^{m-1}$ 个物品 i.

Get 到我的意思了吧. 其实就是把物品的数量拆了, 拆成二进制一点点地加上去, 因为二进制总是很方便.

如果把第 i 种物品拆成体积为 $w[i]\cdot 2^k$ 、价值为 $v[i]\cdot 2^k$ 的物品, 其中 $w[i]\cdot 2^k\leq V$ , 那么空间复杂度就变成了 $O(\log_2{\dfrac{V}{w[i]}})$ , 时间复杂度则变为 $O(NV\log_2{\dfrac{V}{w[i]}})$ .

还是不行吧.

换个思路想一想.

dp[i][j] 表示出在前 i 种物品中选取若干件物品放入容量为 j 的背包所得的最大价值. 现在对第 i 种物品放不放入背包进行决策: 如果不放, 那么 dp[i][j]=dp[i-1][j]; 如果放, 那么背包中应该出现至少一件第 i 种物品, 所以 dp[i][j] 中至少应该出现一件第 i 种物品, 即 dp[i][j]=dp[i][j-w[i]]+v[i]. 为什么会是 dp[i][j-w[i]]+v[i]? 因为 dp[i][j-w[i]] 里可能有、也可能没有第 i 种物品. 我们要确保 dp[i][j] 中至少有一件第 i 件物品, 所以要预留 w[i] 的空间来存放一件第 i 种物品.

状态方程为:

1
2
3
4
if(j>=w[i])
    dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]) //要么不放,要么放且保证背包中至少有一件第i种物品
else
    dp[i][j]=dp[i-1][j]; //背包容量比第i件物品的体积还小,肯定放不下,那就不放

最终代码:

1
2
3
4
5
6
7
8
for(int i=1;i<=N;++i){
    for(int j=1;j<=V;++j){
        if(j>=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        else
            dp[i][j]=dp[i-1][j];
    }
}

模板题: AcWing 1023 买书

Link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n;
int w[5]={0,10,20,50,100};
int dp[1010];//dp[i][j]:买前i本书划掉j元钱的方案数
int main() {
    scanf("%d",&n);
    dp[0]=1;
    for(int i=1;i<=4;++i)
        for(int j=w[i];j<=n;++j)
            dp[j]+=dp[j-w[i]];
    printf("%d\n",dp[n]);
    return 0;
}

模板题: AcWing 1021 货币系统

Link

与上一题 (买书) 不同的是, 这题会爆 int, 因此要用 long long 存储.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,a;
long long dp[3010];
int main() {
    scanf("%d%d",&n,&m);
    dp[0]=1;
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        for(int j=a;j<=m;++j)
            dp[j]+=dp[j-a];
    }
    printf("%lld\n",dp[m]);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.