动态规划-背包DP

背包DP

引入

在具体讲何为背包dp前，先来看如下的例题：

题意概要 有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使得背包中的物品的总价格

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称作0-1背包问题。

0-1背包

解释

例题中已知条件有第i个物品的重量\(w_i\) ，价值\(v_i\) 以及背包的总重量 \(W\)。

设DP状态 \(f_{i,j}\) 为在只能放前 \(i\) 个物品的情况下，容量为 \(j\) 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 \(i-1\) 个物品的情况下，那么对于第 \(i\) 个物品当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 \(f_{i-1,j}\) ；当其放入背包时，背包的剩余容量会减小 \(w_i\) 背包中物品的总价值会增大 \(v_i\) ，故这种情况的最大价值为 \(f_{i-1,j-w_{i}}+ v_i\)

由此可以得出状态转移方程： \[ f_{i,j} = max(f_{i-1,j},f_{i-1,j-w_i}+v_i) \] 这里如果直接采用二维数组对状态进行记录，会出现MLE。可以考虑改用滚动数组的形式来优化。由于对 \(f_i\) 有影响的只有 \(f_{i-1}\) , 可以去掉第一维，直接用 \(f_i\) 来表示处理到当前物品时背包容量为 \(i\) 的最大价值，得出以下方程: \[ f_j = max(f_j,f_{j-w_i}+v_i) \] 务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。

实现

1
2
3
4
5
for(int i=1; i<=n; i++){
    for(int l= W; l>=w[i];l--){
        f[l] = max(f[l],f[l-w[i]]+ v[i]);
    }
}

完全背包

解释

完全背包模型与 \(0-1\) 背包类似，与 \(0-1\) 背包的区别仅在于一个物品可以选取无限次，而非仅能选择一次。

我们可以借鉴 \(0-1\) 背包的思路，进行状态定义：设 \(f_{i,j}\) 为只能选前 \(i\) 个物品时，容量为 \(j\) 的背包可以达到的最大价值。

需要注意的是，虽然定义与 \(0-1\) 背包类似，但是其状态转移方程和 \(0-1\) 并不相同。

过程

可以考虑一个朴素的做法：对于第 \(i\) 件物品，枚举其选了多少个来转移。这样做的时间复杂度时 \(O(n^3)\)的。

状态转移方程如下： \[ f_{i,j} = \max\limits_{k=0}^{+\infty} \left(f_{i-1,j-k\times w_i} + v_i\times k\right) \] 考虑做一个简单的优化。可以发现，对于 \(f_{i,j}\) ，只要通过 \(f_{j,j-w_i}\) 转移就可以了。因此状态转移方程为： \[ f_{i,j} = \max(f_{i-1,j}, f_{i,j-w_i}+v_i) \] 理由时当我们这样转移时，\(f_{i,j-w_i}\) 已经由 \(f_{i,j}-2\times w_i\) 更新过，那么 \(f_{i,j-w_i}\) 就是充分考虑了第 \(i\) 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

多重背包

在原有的0-1背包问题上，第 \(i\) 个物品可被选择 \(k_i\) 次

最朴素的多重背包，就是化成0-1背包的形式，把每 \(k_i\) 个相同的物品当成不同的物品逐个放置，按 0-1 背包做即可。

这个方法简单，但时间、空间复杂度有一定要求

1
2
3
4
5
6
7
for(int i=1;i<=n;i++){
    for(int j=W;j>=w[i];j--){
        for(int k=1;k+w[i]<=j && k<= cnt[i];k++){
            dp[j] = max(dp[j],dp[j-k+w[i]]+k*v[i]);
        }
    }
}

二进制分组

我们发现，上述情况下，相同物品会被重复计算导致计算次数增大。例如，相同物品中，只算一个物品时，会被计算 \(C_n^1\) 次，只算两个物品时，会被计算 \(C_n^2\) …… 。当然，由于用了 \(dp\) ，这里对 \(k_i\) 个物品会计算 \(k_i\times W\) 次。

因此，我们需要减少分组数。

注意到，对于 \(6\) 有 \[ 6 = 011_2 = 11_2 +3 = 1+2+3 \] 对于数 \(n\) ，凡高位有1，都可拆出一个 \(i-1\) 位全 \(1\) 的二进制数，即可表示为 \(1+2+2^2+...\) ，显然 \(1\) 之间的组合可不重复地计算 \([0,2^{i}-1]\) 的每个值，另外加上不能划分的数 \(x\) ，便能计算 \([x,2^{i}-1+x]\) ，即可计算中 \([0,n]\) 的所有情况。因此，只用拆分出 \(\lceil \log_2{(k+1)\rceil}\) 个物品即可。

实现

1
2
3
4
5
6
7
8
9
10
11
12
int cnt = 0;
for(int i=1;i<=m;i++){
    int c=1,p,h,k;
    cin >> p >> h >> k;
    //p为单个物品重量，h为单个物品价值
    while(k<c){
        k-=c;
        w[++cnt] = c*p;
        v[cnt] = c*h;
        c<<=1;
    }
}

单调队列优化

混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 \(k\) 次。

实际上，合并在一起就行了

1
2
3
4
5
6
7
8
for(循环物品种类){
	if 是0-1背包
		套用0-1背包
	else if 是完全背包
		套用完全背包
	else if 是多重背包 (如果用二进制分组就划到0-1背包)
	套用多重背包
}

例题：P1833 樱花 - 洛谷

二维费用背包

P1855 榨取kkksc03

有 $n$ 个任务需要完成，完成第 $i$ 个仍无需要花费 $t_i$ 分钟，产生 $c_i$ 元的开支。

现在有 $T$ 分钟时间， $W$ 元钱来处理这些任务，求最多能完成多少任务

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

这个时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE 。

实现

1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
    for(int i=m;i>=mi;i--){
        for(int j=t;j>=ti;j--){
            dp[i][j] = max(dp[i][j],dp[i-mi][j-ti]+1);
        }
    }
}

分组背包

P1757 通天之分组背包 有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w_i$ ，体积为 $v_i% 。同时，每个物品术语一个组，同组最懂只能选择一个物品，求背包能装在物品的最大总价值。

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 \(t_{k,i}\) 表示第 \(k\) 组的第 \(i\) 件,像图的邻接表存就可以了。甚至你可以用链式前向星来存，不需要存 \(i\) ，用边的编号存权重和价值即可。

作者很想搞怪，这里就用前向星的形式了，可自己想想如何如何用 \(t_{k,i}\) 来做。

思考：和树上背包一样，为什么我们 「分组中选一个」或树上背包时「多个不同物品打包选一组」会在 \(j\) 的循环内先遍历整个分组物品或者每 \(k\) 个一组的物品呢？（当然最外层循环是「遍历每个分组」/「遍历每个儿子」）。实际上，这就是为什么能实现在分组中选一个，和树上背包时不重复选结点的原因。

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
#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
int w[N],v[N],nxt[N],to[N];
int dp[N];
unordered_map<int,int> head;
int cnt = 0;
void add(int a,int b,int c){
    if(!head[c]) head[c] = -1;
    nxt[++cnt] = head[c];
    head[c] = cnt;
    w[cnt] = a;
    v[cnt] = b;
}


int main(){
    int m,n;
    cin >> n >> m;
    int len = 0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        len = max(len,c);
    }
    //注意遍历顺序
    for(int k=1;k<=len;k++)
    for(int j=n;j>=0;j--){
            for(int p=head[k];~p;p=nxt[p]){
                if(j < w[p]) continue;
                dp[j] = max(dp[j],dp[j-w[p]]+v[p]);
            }
        }
    cout << dp[n];
}

有依赖的背包

「Luogu P1064」金明的预算方案 金明有 $n$ 元钱，想要买 $m$ 个物品，第 $i$ 件物品的价格为 $v_i$ ，重要度为 $p_i$ 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主见。 目标是让所有购买物品的 $v_i \times p_i$ 之和最大。