背包 DP

第一次使用 $𝐿 𝐴 𝑇 𝐸 𝑋$

01 背包

朴素

#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;
}

复制

一维优化

#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 维做法

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

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

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

$𝑓 𝑖, 𝑗 = m a x {𝑓 𝑖 - 1, 𝑗 - 𝑣 𝑖 𝑘 + 𝑤 𝑖 𝑘}$

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 维优化

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

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

1	2	3	4
xxx
xxx	xxx
xxx	xxx	xxx
xxx	xxx	xxx	xxx

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

$𝑓 𝑖, 𝑗 = {𝑓 𝑖 - 1, 𝑗 m a x {𝑓 𝑖 - 1, 𝑗, 𝑓 𝑖, 𝑗 - 𝑣 𝑖 + 𝑤 𝑖}, 𝑗 ⩾ 𝑣 𝑖$

代码如下

#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;

复制

滚动数组优化

#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;
}

复制

多重背包

朴素

$𝑁$ 种物品，背包容量为 $𝑉$ ，第 $𝑖$ 件物品最多能选 $𝐶 𝑖$ 个，每件物品占空间 $𝑣 𝑖$ ，价值为 $𝑤 𝑖$

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

$𝑓 𝑖, 𝑗 = m a x {𝑓 𝑖, 𝑗, 𝑓 𝑖 - 1, 𝑗 - 𝐶 𝑖 𝑘 + 𝑤 𝑖 𝑘}$

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

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 物品，但是这样的情况在上文解法中做了两次决策，显然有一种是多余的。
也就是说，接下来的优化方向是减少每次决策所遇到的同数量同种物品，那会联想到什么呢？
想办法把物品分为多个组，使这些组的不同组合能表示出所有数量，于是想到进制，这里采用二进制拆分。

易证，使用 $20, 21, 22, 23 . . . 2 𝑘 - 1$ 能够表示出 $0$ 到 $2 𝑘 - 1$ 之间的所有的数，即二进制计数。也就是说，如果把物品的数量 $𝐶 𝑖$ 拆分成 $20, 21, 22 . . . 2 𝑘 - 1 + 𝑝, 0 \leq 𝑝 < 2 𝑘 - 1$ ，由 $𝑝$ 的范围可得，其中 $20 + . . . 2 𝑘 - 1$ 能够表示出 $[0, 𝑝]$ 的所有整数，然后也能轻松得出 $20 + . . . + 2 𝑘 - 1$ 选出若干与 $𝑝$ 相加能表示出 $[𝑝, 𝑝 + 2 𝑘 - 1]$ 之间所有整数，两个合并即是 $[0, 𝐶 𝑖]$

因此可以将 $𝐶 𝑖$ 拆分为 $𝑘 + 1$ 种新的物品，每种新物品的体积和价值分别为：

$20 \cdot 𝑤 𝑖, 21 \cdot 𝑤 𝑖, 22 \cdot 𝑤 𝑖, \dots, 2 𝑘 - 1 \cdot 𝑤 𝑖, 𝑝 \cdot 𝑤 𝑖 20 \cdot 𝑣 𝑖, 21 \cdot 𝑣 𝑖, 22 \cdot 𝑣 𝑖, \dots, 2 𝑘 - 1 \cdot 𝑣 𝑖, 𝑝 \cdot 𝑣 𝑖$

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

代码来自 GrainRain 's Blog

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背包解题过程

复制

分组背包

$𝑁$ 组物品，第 $𝑖$ 组有 $𝐶 𝑖$ 个物品，第 $𝑖$ 组的第 $𝑗$ 个物品的价值是 $𝑤 𝑖, 𝑗$ ，体积为 $𝑣 𝑖, 𝑗$ ，背包体积为 $𝑀$ ，每组物品只能选择 $1$ 个

直接枚举组时挨个枚举物品就行了。
按照组划分阶段，第 $𝑖$ 组不选则 $𝑓 𝑖, 𝑗 = 𝑓 𝑖 - 1, 𝑗$ ，第 $𝑖$ 组选第 $𝑘$ 个则 $𝑓 𝑖, 𝑗 = 𝑓 𝑖 - 1, 𝑗 - 𝑣 𝑖, 𝑘 + 𝑤 𝑖, 𝑘$

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

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）

A B 都不选
选 B 不选 A
A B 都选

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

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

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