常见背包问题

强烈推荐大佬博客dd大牛的《背包九讲》！！！

01背包问题

01背包问题：指的是每件物品只有一个，背包有容量（或者重量）限制，每个物品有大小（或者重量）和价值，求背包在容量（或者重量）限制下能装入物品的价值和最大是多少。

f[i][j]，代表考虑前i个物品，当前背包容量为j时，背包能装入的最大价值。
f[i][j]=max{f[i][j-1],f[i-1][j-v[i]]+w[i]};表示，
不选第i个物品和选第i个物品，在背包容量为j时，那种情况背包内的价值最大
可以画二维表格，更容易理解
1
2
3
4

01背包问题模板题

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
int f[N][N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    cout<<f[n][m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优化空间

考虑对空间复杂度进行优化，f[i][j]是由f[i-1][i~j]来产生的，所以我们只需要保留上一行的信息，不需要其他行的信息。考虑用1行来存储，那么如何获得上一行的信息呢？每一行倒着遍历即可，这样一行原本信息f[i][j]=f[i-1][j]，判断是否拿第i个物品时，j>j-v[i],也不会产生冲突。

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
int f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)//从大到小枚举，保证第i次是通过i-1得来的
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完全背包问题

完全背包问题在01背包问题上的改变是不限制物品的数量，即每样物品有无数个，求背包能装入物品的价值和最大是多少

考虑从01背包推导至完全背包

for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)//从大到小枚举，保证第i次是通过i-1得来的
        for(int k=1;k*v[i]<=j;k++)  f[j]=max(f[j],f[j-v[i]*k]+w[i]*k);
1
2
3

考虑另一种思路：

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

这个代码与01背包问题的代码的差别只是在遍历背包容量时，是从小到大遍历的，思考一下，为什么要这样做？

01背包问题从大到小遍历，是为了背包容量为 j 时，保证此时的f[ i ][ j ]是从f[i-1][ j （不选）]或者f[i-1][j-v[i]]+w[i]（选一个第 i 个物品）得来的,也就是说明，在考虑第 i 个物品，背包容量为 j 时，该物品 i 只会被考虑加入背包一次。

那么为什么 j 从小到大遍历后，就会转化为完全背包问题呢？
j 从小到大遍历时，当前的f[ i ][ j ]是从f[i-1][ j ]（不选）或者f[ i ][j-v[ i ]]+w[ i ]（选择一个或多个第 i 个物品 ）得来的，当f[ i ][ j ]由f[ i ][j-v[ i ]]+w[ i ]的来时（f[ i ][j-v[ i ]]也可能选择了第 i 个物品），此时第 i 个物品被选择了多个。这样就从小到大遍历 j 就将第 i 个物品给考虑了多次。

完全背包问题模板题

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
int f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

多重背包问题

多重背包问题在01背包的基础上，物品有了数量的限制。

转化为01背包问题求解

可以将多重背包问题转化为01背包问题来求解，只需要在01背包的基础上怎加一层循环，来遍历物品的数量即可，该方法只能用于数据范围比较小的情况。
多重背包问题 I 模板题

代码如下:

#include
#include
#include
#include
using namespace std;

const int N=1e2+10;

int f[N];
int v[N],w[N],cnt[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>cnt[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            for(int k=1;k<=cnt[i];k++) 
                if(j>=k*v[i]) f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
    cout<<f[m];
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二进制优化

多重背包二进制优化解法的思路仍然是将多重背包问题给分解成01背包问题求解，如果将物品给拆成一份一份的情况，那么就跟上一个解法一样。二进制优化就是在拆分方法上做优化，我们不必要将物品数量给拆成一份一份的，用二进制拆分的方法。
将一个数n拆分成：1+2+4+…+2^k+剩余的数
例如：7=1+2+4，8=1+2+4+1
可以证明，0-n中的任意一个数，均可以用若干n拆分出的系数来表示
例如：7=1+2+4
1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=7

这样便可将问题给优化了，当物品数量为s时，只需要拆分成log(s)个数而不是s个，在代码中能有效降低时间复杂度
多重背包问题 II 模板题

代码如下：

#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;

int f[N];

int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int> > ve;
    for(int i=0;i<n;i++){//拆分
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        for(int j=1;j<=s;j*=2){
            s-=j;
            ve.push_back(make_pair(v*j,w*j));
        }
        if(s) ve.push_back(make_pair(v*s,w*s));
    }
    for(int i=0;i<ve.size();i++)//按照01背包计算
        for(int j=m;j>=ve[i].first;j--)
            f[j]=max(f[j],f[j-ve[i].first]+ve[i].second);
    cout<<f[m];
    
    return 0;
}
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

单调队列优化

当数据范围再次变大时，考虑更加优化的方法—利用单调队列优化
多重背包问题的单调队列优化方法，就是传说中的《男人八题》

这个问题比较难，我大概能理解，但是讲不好，建议找视频学习。
多重背包问题 III 模板题

代码如下：

#include 
#include 
using namespace std;
const int N = 20010;
int dp[N], pre[N], q[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        memcpy(pre, dp, sizeof(dp));
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++j) {
            int head = 0, tail = -1;
            for (int k = j; k <= m; k += v) {
                if (head <= tail && k - s*v > q[head])
                    ++head;
                while (head <= tail && pre[q[tail]] - (q[tail] - j)/v * w <= pre[k] - (k - j)/v * w)
                    --tail;
                if (head <= tail)
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head])/v * w);
                q[++tail] = k;
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}
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

混合背包问题

混合背包问题就是将上述三种背包问题混合在一起的情况
其中多重背包问题可二进制拆分成01背包问题
01背包问题与完全背包问题分开计算即可
混合背包问题模板题

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=1e3+10;
int n,m;
int f[N];//多重背包问题转化为01背包问题，分类讨论
struct node{
    int kind;
    int v,w;
};
int main()
{
    vector<node>v;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int x,y,s;
        scanf("%d%d%d",&x,&y,&s);
        if(s<0) v.push_back({-1,x,y});
        else if(s==0) v.push_back({0,x,y});
        else
        {
            for(int k=1;k<=s;k*=2)
            {
                s-=k;
                v.push_back({-1,k*x,k*y});
            }
            if(s) v.push_back({-1,s*x,s*y});
        }
    }
    vector<node>::iterator it;
    for(it=v.begin();it!=v.end();it++)
        if((*it).kind==-1) 
            for(int j=m;j>=(*it).v;j--)
                f[j]=max(f[j],f[j-(*it).v]+(*it).w);
        else 
            for(int j=(*it).v;j<=m;j++)
                f[j]=max(f[j],f[j-(*it).v]+(*it).w);
    printf("%d\n",f[m]);
    return 0;
}
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
42
43

二维费用的背包问题

二维费用的背包问题指的是背包有多个限制，这个问题比较简单，只需要稍微改变一下01背包问题即可，容易理解
二维费用的背包问题模板题

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=110;
int f[N][N];
int n,v,m;
int main()
{
    cin>>n>>v>>m;
    for(int i=0;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        for(int j=v;j>=x;j--)
            for(int k=m;k>=y;k--)
                f[j][k]=max(f[j][k],f[j-x][k-y]+z);
    }
    cout<<f[v][m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

分组背包问题

给定n组物品，每组物品若干个，同一组物品最多只能选择一个。每组s个，一共s+1种选择(不选也算一种)，求背包在容量（或者重量）限制下能装入物品的价值和最大是多少。

分组背包问题就是在01背包的基础上，增加对组内每个物品的遍历即可
分组背包问题模板题

代码如下：

#include
#include
#include
#include
using namespace std;
const int N=110;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int t;
        scanf("%d",&t);
        for(int j=0;j<t;j++) scanf("%d%d",&v[j],&w[j]);
        for(int j=m;j>=0;j--)
            for(int k=0;k<t;k++)
                if(v[k]<=j)  f[j]=max(f[j],f[j-v[k]]+w[k]);
    }
    cout<<f[m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

总结

各种背包问题的原型是01背包问题，所以要弄明白01背包问题。