发布于 ，更新于 

背包 DP

第一次使用 \(\LaTeX\)

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
29
30
31
32
#include <iostream>
#include <algorithm>
#define MAXN 1010

using namespace std;

int n, m;
int v[MAXN], w[MAXN];
int f[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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
21
22
23
24
25
26
27
28
#include <iostream>
#define MAXN 1010

using namespace std;

int n,m;
int v[MAXN],w[MAXN];
int f[MAXN];

int main() {
    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 个）物品枚举
            f[j] = max(
                f[j], // 此时未更新的 f[j] 是上一次（i-1）枚举的数据，即 f[j] 是不选第 i 个物品的 f[j]
                f[j - v[i]] + w[i]
                );
        }
    }

    cout << f[m] << endl;

    return 0;
}

完全背包

朴素做法

即 3 维做法

先考虑状态，容易想到选到某个位置后，其特征有空间，物品种类和价值。价值是要求的，所以我们可以开二维状态，分别表示空间和物品种类。即 \(f_{i,j}\) 表示从前 \(i\) 种物品里选，占了 \(j\) 单位空间的最大收益。
参考 lzp 大佬博客中的要求，这个状态是否能保证唯一且可递推呢？

  • 唯一：选物品的范围确定，所占用的空间确定，在所有方案中存储最大收益的方案。由于空间确定，因此不会影响后面决策，此时一定能保证最优且唯一。
  • 可递推：前面最优，容易想到通过枚举新拿的物品数量求得当前最优方案（后面讲）

接下来讲递推过程：
前面 0/1 背包我们只需要考虑一个物品是否选，但是现在还需要考虑选多少。
考虑是否选择时，我们直接枚举当前物品的状态，即 0/1，选或不选。
放到现在这个题目中，把刚才 0/1 背包枚举选或不选的过程看作枚举物品数量，即选 \(1\) 个或选 \(0\) 个，这启发我们可以通过枚举物品数量来解决选多少的问题。
状态转移方程就自然而然地出来了：

\[ f_{i,j} = \max \left\{ f_{i-1,j-v_ik} + w_ik \right\} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int backpack() {
    #define MAXN 1010

    using namespace std;

    int n,m; //! 应当定义在函数外部，原因我不说，因为没人看
    int v[MAXN],w[MAXN];
    int f[MAXN][MAXN];

    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 - v[i] * k] + w[i] * k);
        }
    cout << f[n][m] << endl;
}

2 维优化

上面的转移有三维！太慢了！想办法如何减去一个维度。

状态方面，没有办法再降了，因为去掉任意一维都会导致无法表示唯一的状态。
那就考虑优化递推的过程。想一想是否有哪些状态能够转移到当前状态但是没考虑到？答案是有的。
考虑递推过程的第二层、第三层循环，对于每一个体积 \(j\)，\(k\) 都需要从 \(1\) 枚举到 \(j/v_ik\) ，形象点来说大概长这样

1234
xxx
xxxxxx
xxxxxxxxx
xxxxxxxxxxxx

显然，\(k = 1,2,3\) 时都重复地枚举了待转移状态，想办法把这些冗余的东西去掉——直接从算过 \(k=1,2,3\) 的状态转移过来。
这意味着我们不能再单纯的用物品数量进行递推。观察第一行到第二行，容易发现在满体积的时候，第二行只是比第一行多了一个物品 \(i\) 而已。
讨论单个物品是否选择，于是新的递推方式就显而易见了，设当前状态为 \(f_{i,j}\)，我既可以选一个物品 \(i\)，也可以不选一个物品 \(i\)，从 \(f_{i-1,j}\) 转移过来。
状态转移方程：

\[ f_{i,j} = \begin{cases} f_{i-1,j} \newline \max \left\{ f_{i-1,j}, f_{i,j-v_i} + w_i \right\},\ j\geqslant v_i \end{cases} \]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define MAXN 1010

using namespace std;

int n,m;
int v[MAXN],w[MAXN];
int f[MAXN][MAXN];


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 - v[i] * k] + w[i] * k);
		f[i][j] = f[i - 1][j];
		if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
	}
cout << f[n][m] << endl;

滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAXN 1010

using namespace std;

int n,m;
int v[MAXN],w[MAXN];
int f[MAXN][MAXN];

int backpack() {
    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[i][j] = f[i - 1][j]; 恒等式直接删除
            // if (j >= v[i]) 直接从 v[i] 开始循环就完事了
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    cout << f[m] << endl;
}

多重背包

朴素

\(N\) 种物品，背包容量为 \(V\)，第 \(i\) 件物品最多能选 \(C_i\) 个，每件物品占空间 \(v_i\)，价值为 \(w_i\)

第一种容易想到的解法是把完全背包的方法拿来用，因为多重背包只是加了 \(k\) 的限制。 状态转移方程：

\[ f_{i,j} = \max\{f_{i,j}, f_{i-1,j - C_ik} + w_ik\} \]

考虑多重背包和完全背包的区别可以发现，多重背包虽然每种物品不只一种，但是有确定的数量，而完全背包没有数量限制，则可以轻松地在忽略时间复杂度的情况下把多重背包拆分成 01 背包，即把 \(M_i\) 件第 \(i\) 件物品挨个算单个物品再按照 01 背包的方式处理。

1
2
3
4
5
6
7
for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= m; ++ j) {
        for (int k = 0; k <= min(c[i],j/w[i])/* 数量和体积两个都限制数量 */; ++ k) {
            f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
        }
    }
}

二进制优化

这种暴力方式求解比较慢，容易发现，在求解过程中，每个同种物品是按照不同种物品进行处理的，换句话说，我选第一个 a 物品与选第二个 a 物品，实际上效果都是选 1 个 a 物品，但是这样的情况在上文解法中做了两次决策，显然有一种是多余的。
也就是说，接下来的优化方向是减少每次决策所遇到的同数量同种物品，那会联想到什么呢？
想办法把物品分为多个组，使这些组的不同组合能表示出所有数量，于是想到进制，这里采用二进制拆分。

易证，使用 \(2^0, 2^1, 2^2, 2^3... 2^{k-1}\) 能够表示出 \(0\) 到 \(2^{k-1}\) 之间的所有的数，即二进制计数。也就是说，如果把物品的数量 \(C_i\) 拆分成 \(2^0, 2^1, 2^2...2^{k-1} + p,0 \leq p < 2^{k-1}\)，由 \(p\) 的范围可得，其中 \(2^0+...2^{k-1}\) 能够表示出 \([0,p]\) 的所有整数，然后也能轻松得出 \(2^0+...+2^{k-1}\) 选出若干与 \(p\) 相加能表示出 \([p,p+2^k-1]\) 之间所有整数，两个合并即是 \([0,C_i]\)

因此可以将 \(C_i\) 拆分为 \(k+1\) 种新的物品，每种新物品的体积和价值分别为：

\[ \begin{aligned} &2^0 \cdot w_i,2^1 \cdot w_i,2^2 \cdot w_i,\dots,2^{k-1} \cdot w_i,p \cdot w_i \newline &2^0 \cdot v_i,2^1 \cdot v_i,2^2 \cdot v_i,\dots,2^{k-1} \cdot v_i,p \cdot v_i \end{aligned} \]

拆分完再进行 01 背包即可。

代码来自 GrainRain 's Blog

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
const int N = 25000;
// 一共有 1000 项，每项最多拆分成 log s 项
const int M = 2010;

int n, m;
int v[N], w[N];
int f[N];

cin >> n >> m;

int cnt = 0;
for (int i = 1; i <= n; i ++) {
    int a, b, s;
    cin >> a >> b >> s;

    for (int k = 1; k <= s; k *= 2) { // 从2^0 开始枚举 2 的次幂
        s -= k;
        v[++ cnt] = a * k;
        w[cnt] = b * k;
    }
    if (s > 0) {
        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] << endl;
// 01背包解题过程

分组背包

\(N\) 组物品，第 \(i\) 组有 \(C_i\) 个物品，第 \(i\) 组的第 \(j\) 个物品的价值是 \(w_{i,j}\)，体积为 \(v_{i,j}\)，背包体积为 \(M\)，每组物品只能选择 \(1\) 个

直接枚举组时挨个枚举物品就行了。
按照组划分阶段，第 \(i\) 组不选则 \(f_{i,j} = f_{i-1,j}\)，第 \(i\) 组选第 \(k\) 个则 \(f_{i,j} = f_{i-1,j-v_{i,k}} + w_{i,k}\)

这里直接给出数组删维优化过的代码

1
2
3
4
5
6
7
for (int i = 1; i <= n; ++ i) {
	for (int j = m; j >= m; -- j) {
		for (int k = 1; k <= c[i]; ++ k) {
			f[i][j] = max(f[j], f[j-v[i][k]] + w[i][k]);
		}
	}
}

依赖背包

我的 Windows 盘还剩 5 个 G，新买的东方冰之勇者记占 2G,LLVM 依赖于 MSVC 生成工具，MSVC 占用 2G 磁盘，LLVM 占用 2G 磁盘，问我应该怎么安装收益最大
reboot to archlinux!

A 物品依赖于 B，选 B 物品之前需要先选 A 物品，问最大价值

容易发现对于任意有依赖关系的物品 A B 来说，一共有以下三种可能的决策
（A 依赖 B）

  1. A B 都不选
  2. 选 B 不选 A
  3. A B 都选

因为这三种情况只会出现一个，联想分组背包的特征，将这三种情况每个看成一个组里的物品，即转化为了分组背包。

当成树形 DP 好做一点，加到 TODO 里面。

许可协议

本文采用 GNU 自由文档许可证 许可协议，转载请注明出处。

分享文章