背包DP

背包DP

九月 01, 2021

背包

问题：有n个物品，每个重量为vi,权值为wi，每个物品仅用一次,问在背包容量为W里能装的最大价值

01背包

核心特点：每件物品最多只能用一次
集合条件：

核心：不漏下任何一个

1.只从前i个物品中选
2.总体积$\le$V

属性：Max

$f_{i,j}$据上面的假设，意义应该是在前i个物品，当前已选的物品的最大价值

把$f_{i,j}$表示的所有选法分为两大类：

1.不选第i个物品
2.选第i个物品

计算：$f_{i,j}$

如果是第1类的话显然

第2类的话我们考虑：
$f_{i,j}$应该可以从上一个位置推过来
那么上一个位置的背包容量应该就是 j-v[i]

同时由于第i位的东西必须选
所以说这个位置的转移方程应该是

综上：我们要的应该是两个集合的最大值 所以说：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N],f[N][N];
int main(){
    ios::sync_with_stdio(false);
    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=0;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;
}

此时我们还可以考虑到一个问题我们发现第i个物品一定是从上一个物品的某一个体积的背包里整过来的

那么我们就可以考虑空间的优化

$f_{j}$让它表示背包容量为j时的最大容积即可

那么我们看一下第二重循环

1
2
3
4
for(int j=0;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]);
}

这个我们直观考虑应该写成这样

1
2
3
4
for(int j=0;j<=m;j++){
    f[j]=[j];
    if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
}

首先我们看f[j]=f[j]显然是一句废话，删掉就行

$f[j]$的转移看着也没太大毛病

等等，还有点问题

首先，由于我们枚举的是体积，那么问题应该在于当j<v[i]时，这个转移显然时废掉了（j-v[i]此时显然小于0）
所以我们可以从v[i]开始枚举

其次，我们考虑一下，我们的第i种状态是不是都是从i-1转移而来的

所以我们的此时是不是也应该做到我们每次取max的两个数也要是上一重循环的数，而不能是这次已经覆盖过的，因此，我们要从m枚举到v[i]

综上所述：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int n,m;
int v[N],w[N],f[N][N];
int main(){
    ios::sync_with_stdio(false);
    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--) 
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

完全背包

核心特点：每件物品可以装无限次

假设每一个物品背包装满时最多选k个

那么转移方程很显然

那么很容易得到朴素做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10;
int v[N],w[N],f[N][N];
int n,m;
int main(){
    ios::sync_with_stdio(false);
    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=0;j<=m;j++){
            for(int k=0;k*v[i]<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j - k * v[i]]+ k * w[i]);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

但是这样是三重循环预计连1000 1000的数据都过不了，考虑优化

我们可以把右边的玩意们列出来：

然后我们再写一个式子

观察相似之处,我们发现第一个的那个式子除了第一个以外，其余的显然都是等于$f_{i,j-v[i]}+w[i]$的

所以原式就可以轻易的化为

瞬间干掉了k所在的那个循环

而且我们借用上一个题的那个思想，空间方面i的这一层显然也可以干掉

最终式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10;
int v[N],w[N],f[N];
int n,m;
int main(){
    ios::sync_with_stdio(false);
    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;
}

多重背包

核心特点：每件物品最多有Si个

朴素做法的话和刚才的朴素写法一样

我们先把式子写出来

二进制优化

前置知识，一个数一定可以用$2^n$的数拼凑出来

原因：1,2 可以凑出来1~3

1~3分别加上4就是1~7

同理也可以加上8

证毕（其实很显然啊喂）

然后我们就可以将1,2,4,8,16,32,64,128,256，c……分别打包成一个区间

（$1+2+4……2^k+c=s$，$2^k＜c<2^k+1$）

然后很显然我们就可以把它转化成01背包问题了

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2e4+10;
int w[N],v[N],f[N];
int n,m,cnt;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a,b,s,k=1;
        cin>>a>>b>>s;
        while(k<=s){
            v[++cnt]=a*k;
            w[cnt]=b*k;
            s-=k; k*=2;
        }
        if(s) v[++cnt]=a*s,w[cnt]=b*s;
    }
    n=cnt;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}

由于担心大家记混，我总结出了一个小技巧：

对于前面的三个背包,只有完全背包是从小到大枚举空间，其余的一定是从大到小

时间复杂度：$O(n^2logn)$

单调队列优化

我们直接把式子全部列出来，会发现下面的性质：

其实上下我们发现是不能乱搞的，因为还有$f_{i-1,j}$和$f_{i-1,j-(s+1)v}+sw$是空白的

image-20211029180900981

所以我们就可以直接用长度为s的互动窗口，维护每个窗口的最大值

分组背包

核心特点：有若干组，每组里面最多选一个物品（假如说有个瓜摊，选了生瓜蛋子就不能选熟瓜了）

状态转移：

若选这一组的东西 $f_{i,j}=f_{i-1,j-v[i][k]}+w[i][k]$

若不选的话： $f_{i,j}=f_{i-1,j}$

求两个集合的最大值：取Max

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