[算法汇总]背包dp
Nickel_Angel
2019-06-17 21:31:51
这里是背包dp的例题剖析 $QwQ$ ~~
首先[背包九讲](https://blog.csdn.net/yandaoqiusheng/article/details/84782655)了解一下(￣▽￣)
在这里~~详细~~解释一下背包九讲的多重背包中的单调队列优化：
（下文 $v[i], c[i], p[i]$ 分别表示了第$i$件物品的体积，价值，数量，$V$则表示了背包的总体积）
其主要思想是，由于多重背包中时间复杂度为 $O(nV \times \sum p[i])$ 的朴素做法的状态转移方程为：
$$
dp[i][j] = \max_{0 \le k \le p[i], k \times v[i] \leq j}(dp[i - 1][j - k \times v[i]] + k \times c[i]) \quad (j \in [0, V])
$$
注意到 $dp[i][j]$ 只能由 $dp[i - 1][j - k \times v[i]]$ 转移过来，而 $j - k \times v[i]$ 和 $j$ 除以 $v[i]$ 均有相同的余数，即两个状态之间能进行转移，其中有一个条件是它们第二维的值模 $v[i]$ 得到的余数相同。故我们可以根据状态第二维模 $v[i]$ 得到的余数，对状态进行分类。由于只有在同类之间，状态才可以进行转移，所以我们考虑对于每一个类分别进行状态转移。
下面我们考虑采用同类之间分开转移的方法后，状态转移方程应该如何写。注意在下面的式子中，$j$ 是我们枚举的余数，和上面提到朴素做法中 $j$ 的含义不再一样。
我们枚举余数 $j$ 后，考虑对于同一类的状态，它们的一般形式为 $dp[i][j + l \times v[i]]\,(j + l \times v[i] \le V)$，当 $k \le k'$ 且 $k' - k \le p[i]$ 时，$dp[i - 1][j + k \times v[i]]$ 就可以转移到 $dp[i][j + k' \times v[i]]$，我们可以根据此来列出如下状态转移方程：
$$
dp[i][j + k' \times v[i]] = \max_{k \ge 0, k' - p[i] \le k \le k'}(dp[i - 1][j + k \times v[i]] - k \times c[i] + k' \times c[i]) \quad (j \in [0, v[i] - 1], k' \ge 0, j + k' \times v[i] \le V)
$$
我们现在需要做的就是找到 $dp[i][j + k' \times v[i]]$ 的最佳决策点。不难发现方程右边 $k' \times c[i]$ 是可以提出 $\max$ 的，将其提出后方程变为：
$$
dp[i][j + k' \times v[i]] = \max_{k \ge 0, k' - p[i] \le k \le k'}(dp[i - 1][j + k \times v[i]] - k \times c[i]) + k' \times c[i] \quad (j \in [0, v[i] - 1], k' \ge 0, j + k' \times v[i] \le V)
$$
这个方程的关键目标是求在所有满足 $k \ge 0, k' - p[i] \le k \le k'$ 的 $k$ 中，$dp[i - 1][j + k \times v[i]] - k \times c[i]$ 的最大值，显然由于我们是先枚举 $i, j$，后枚举 $k$，故 $i,j$ 可以看作是已经给定的，进而 $k$ 能直接决定 $dp[i - 1][j + k \times v[i]] - k \times c[i]$ 的值，这样我们就可以将方程的关键目标转化为对于一个序列的每一个位置 $k'$，求序列在区间 $[\max(0, k' - p[i]), k']$ 最大值的问题，使用单调队列解决即可。
Code：
```cpp
struct node
{
int t, val;
node() {}
node(int t, int val) : t(t), val(val) {}
}q[MAXN];
inline int multi_pack(int n, int V, int *v, int *c, int *p)
{
int dp[V], res = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i)
{
for (int head, tail, bound, j = 0; j < v[i]; ++j)//枚举剩余系的余数
{
head = 1, tail = 0;
bound = (V - j) / v[i];//计算在本剩余系下的转移次数
for (int now, k = 0; k <= bound; ++k)
{
now = dp[j + k * v[i]] - k * c[i];
while (head <= tail && now >= q[tail].val) --tail;//维护队列单调
q[++tail] = node(k, now);
while (head <= tail && q[head].t < k - p[i]) ++head;
//由于最多只能选p[i]件,故进队时间在k - p[i]之前的值出队
dp[j + k * v[i]] = q[head].val + k * c[i];
res = max(res, dp[j + k * v[i]]);
//由于是每个剩余系单独dp,故要有中间变量记录最值
}
}
}
return res;
}
```
将这个代码稍作修改便可通过[P1776 宝物筛选](https://www.luogu.org/problemnew/show/P1776)
某些题可以~~(贪心)~~归约为背包问题，如：
[P1282 多米诺骨牌](https://www.luogu.org/problemnew/show/P1282)
看起来似乎与背包无关，但……
我们设$dp[i][j]$表明前$i$个数字，第一行数字和为$j$时的最小交换次数。
所以有：
$$ dp[i][j] = \begin {cases} min(dp[i][j], dp[i - 1][j - U[i]]) & \text {如果当前不交换，其中$j \geq U[i]$} \\ min(dp[i][j], dp[i - 1][j - D[i]] + 1) & \text {如果当前交换，其中$j \geq D[i]$} \end {cases} $$
其中$U[i]$，$D[i]$分别为第$i$个骨牌上方块中的点数与下方块中的点数。
仔细观察，不难发现这与01背包的状态转移方程相似……
由于骨牌点数为$1$~$6$故背包体积为$6 \times n$；
最后找$dp[n][i] (i \leq 6 \times n)$中合法的答案即可……
然后本题愉快结束$QAQ$
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int n, U[1010], D[1010], dp[1010][6010], sum = 0;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", U + i, D + i);
sum += U[i] + D[i];//sum记录点数之和，方便最后找答案
}
memset(dp, 0x3f, sizeof(dp));//dp初始化为inf
dp[1][D[1]] = 1, dp[1][U[1]] = 0;//初始化
for (int i = 2; i <= n; ++i)
{
for (int j = 0; j <= 6 * n; ++j)
{
if (j >= U[i]) dp[i][j] = min(dp[i][j], dp[i - 1][j - U[i]]);
if (j >= D[i]) dp[i][j] = min(dp[i][j], dp[i - 1][j - D[i]] + 1);
}
}
int mind = 0x3f3f3f3f, mint = 0x3f3f3f3f;
//mind为最小差值，mint为答案
for (int i = 0; i <= sum; ++i)
{
if (dp[n][i] != 0x3f3f3f3f)
{
if (abs(i - (sum - i)) < mind)
{
mind = abs(i - (sum - i));
mint = dp[n][i];
}
else if (abs(i - (sum - i)) == mind) mint = min(mint, dp[n][i]);
}
}
printf("%d", mint);
return 0;
}
```
[P1941 飞扬的小鸟](https://www.luogu.org/problemnew/show/P1941)
由于小鸟可以**无限**向上飞(除非碰到边界)或向下降**一次**，所以本质上：
上升为**完全背包**，下降为**01背包**，即：
将体积为$x_i$的$n$种物品(每种物品有无限个)装入容量为$m$背包中且在装第$i$个物品时，背包内的物品所占容量不少于
$low_i$且不多于$high_i$，若$i$时刻选择不装则背包内的物品所占容量自动减少$y_i$，求最终最少能装的物品数量……
(若无解则输出在满足条件的情况下最多装几个物品$qwq$)
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, k, x[10010], y[10010], low[10010], high[10010], dp[10010][2010];
bool tube[10010];//记录i位置是否有水管
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &x[i], &y[i]);
low[i] = 1, high[i] = m;
}
for (int i = 1, a, b, c; i <= k; ++i)
{
scanf("%d%d%d", &a, &b, &c);
tube[a] = true;
low[a] = b + 1;
high[a] = c - 1;
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= m; ++i) dp[0][i] = 0;//注意初始化
for (int i = 1; i <= n; ++i)
{
for (int j = x[i] + 1; j <= m + x[i]; ++j)
dp[i][j] = min(dp[i][j - x[i]], dp[i - 1][j - x[i]]) + 1;
//在上升时可选择继承本时刻跳跃的状态或直接从上一时刻跳跃过来
for (int j = m + 1; j <= m + x[i]; ++j)
dp[i][m] = min(dp[i][j], dp[i][m]);
//题目中“小鸟高度为 m 时，无法再上升”故高度超过m的状态均视为到达m
for (int j = 1; j <= m - y[i]; ++j)
dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i]]);
//这里未使用滚动数组且状态转移方程发生了一些转化(- 变为 +),故01背包更新顺序为正序
for (int j = 1; j < low[i]; ++j)//将出界的状态清除
dp[i][j] = inf;
for (int j = high[i] + 1; j <= m; ++j)
dp[i][j] = inf;
}
int ans = inf;
for (int i = 1; i <= m; ++i) ans = min(ans, dp[n][i]);
if (ans < inf) printf("1\n%d", ans);
else
{
ans = 0;
int far = 0;
for (int i = n, j; i > 0; --i)
{
for (j = 1; j <= m; ++j)
{
if (dp[i][j] < inf)
{
far = i;
break;
}
}
if (j <= m) break;//注意这里j <= m表明j未正常跳出循环,说明已统计到答案,跳出循环即可
}
for (int i = 1; i <= far; ++i)
{
if (tube[i]) ++ans;
}
printf("0\n%d", ans);
}
return 0;
}
```
[P5322 [BJOI2019]排兵布阵](https://www.luogu.org/problemnew/show/P5322)
由于每个城堡得分独立，本题可将城堡看成物品，发现对于每个城堡（设其编号为 $i$），**将 $s$ 个玩家部署的士兵数从小到大排序后**，如果第 $k$ 个玩家部署的士兵数（即 $s$ 个玩家在该城堡部署的士兵数中，第 $k$ 小的值）的 $2$ 倍严格小于小C部署的士兵数 $j$，则前 $k$ 个玩家在该城堡内部署的士兵数的 $2$ 倍均严格小于小C部署的士兵数 $j$ ，那么小C在这个城堡的得分为 $k \times i$。由于我们希望用尽可能少的兵力得到 $k \times i$ 的分数（设第 $k$ 名玩家在该城堡部署的士兵数为 $a$），则我们只需向该城堡部署 $2a + 1$ 个士兵即可。
于是设 $dp[i][j]$ 为在考虑前 $i$ 个城堡，向前 $i$ 个城堡部署的士兵数总和为 $j$ 时的最大得分，$a[i][k]$ 为第 $i$ 个城堡，$s$ 个玩家在该城堡部署的士兵数中，第 $k$ 小的值，不难想出转移方程：
$$dp[i][j] = max(dp[i - 1][j - 2 \times a[i][k] - 1] + k \times i)\,(j > 2 \times a[i][k])$$
其中 $i$ 那一维可用滚动数组优化掉，减少空间复杂度。
时间复杂度 $O(nms)$。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
namespace Primary
{
int s, n, m, a[110][110], dp[20010];
void main()
{
scanf("%d%d%d", &s, &n, &m);
for (int i = 1; i <= s; ++i)
{
for (int j = 1; j <= n; ++j)
{
scanf("%d", &a[j][i]);
}
}
for (int i = 1; i <= n; ++i)
sort(a[i] + 1, a[i] + s + 1);
for (int i = 1; i <= n; ++i)
{
for (int j = m; j >= 0; --j)
{
for (int k = 1; k <= s; ++k)
{
if (j > 2 * a[i][k])
dp[j] = max(dp[j], dp[j - 2 * a[i][k] - 1] + k * i);
}
}
}
int ans = 0;
for (int i = 0; i <= m; ++i)
ans = max(ans, dp[i]);//注意 dp 结束后,循环一遍取最优解
printf("%d", ans);
}
}
int main()
{
Primary::main();
return 0;
}
```
[P3188 [HNOI2007]梦幻岛宝珠](https://www.luogu.org/problem/P3188)
我们可以看出，本题显然是一个 01 背包，但数据范围导致我们不能用 01 背包的经典做法解出这道题。
我们发现题目中有一个比较特殊的性质：
> 保证 $weight_i$ 能写成 $a \times 2^b \text{ }(1 \le a \le 10,0 \le b \le 30)$ 的形式。
即每个物品可以用一个二进制位表示。发现 $b$ 的取值最多有 $31$ 种，故可以考虑先将 $b$ 相同的物品分为一类，先对每一类物品做一次 $dp$ 。下文我们将 $weight$ 值能写成形如 $a \times 2^i$ 形式的物品叫做第 $i$ 类物品。
即设 $f[i][j]$ 表明考虑第 $i$ 类物品时，背包体积为 $j \times 2^i$ 时得到的最大价值。由于题目保证宝石总重量不超过 $W$，进而得出对于每类物品 $j \times 2^i$ 一定不超过 $W$，故我们这样做不用考虑 $j \times 2^i$ 超过 $W$ 的可能。
发现 $f[i][j]$ 的转移和 01 背包的转移无本质区别，而不难发现对于第 $k$ 个物品，设其为第 $i$ 类物品，则必然有 $weight_k = a \times 2^i$，可知 $weight_k >> i = a$，故：$f[i][j] = max(f[i][j - (weight_k >> i)]) + value_k$，其中 $k$ 为第 $i$ 类物品，`>>` 和下文的 `bitand`，`bitor`分别代表二进制运算中的左移，按位与和按位或。
接下来考虑各类物品的答案如何合并到一起。由于 $W \text{ bitand } (2^i - 1)$ 意为 $W$ 二进制的前 $i - 1$ 位，而上文中我们设计的状态是用 $j \times 2^i$ 来表示的。故可以考虑我们依次将 $W$ 的各二进制位的答案从小到大合并到 $j \times 2^i$ 这个状态中。
即考虑设 $g[i][j]$ 表明在考虑前 $i$ 类物品，背包体积为 $j \times 2^i + W \text{ bitand } (2^i - 1)$ 时获得的最大价值。这样我们可以通过位运算的形式将 $W$ 的各二进制位从小到大填入到 $j \times 2^i$ 中，即：
$$g[i][j] = max(f[i][j - k] + g[i - 1][k \times 2 + (W >> (i - 1) \text{ bitand } 1)])\,(0 \leq k \leq j)$$
上方转移分为两个部分，先考虑 $g$ 中位运算的正确性，不难发现，上方式子相当于我们在外层枚举 $i$，依次将 $W$ 的各二进制位的答案合并 $j \times 2^i$ 这个状态中。再考虑除位运算部分外的正确性，我们不难发现 $k \times 2 \times 2^{i - 1} = k \times 2^i$，而 $k \times 2^i + (j - k) \times 2^{i} = j \times 2^i$，进而得出转移是正确的。
不难发现上述转移可以通过滚动 $f$ 数组实现。
考虑转移的边界问题，记录一个 $w[i]$ 表示第 $i$ 类物品中 $j$ 最大为多少。在刷 $f$ 数组的过程中考虑到 $f,g$ 数组的定义，由于每一次从第 $i$ 类物品转移其后继物品背包体积均扩大了 $2$ 倍，而我们设计状态时边界为 $(j + 1) \times 2^i$，故只有当我们选用上取整时 $w'[i]$ 才会落在区间 $[j \times 2^i,(j + 1) \times 2^i]$，转移 $g$ 时边界为 $w'[i] = w[i] + \lceil \frac {w'[i - 1]} {2} \rceil$，故做一个递推即可。
我们应求出 $W$ 二进制位最大的那位 $1$ 的位置，设其为 $len$，则显然 $g[len][1]$ 为答案。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
namespace Primary
{
int n, m, w[40], f[40][1200];
vector<int> W[40], V[40];
void main()
{
scanf("%d%d", &n, &m);
while (n != -1)
{
int len = 0;
for (int i = 1, x, y, p; i <= n; ++i)
{
scanf("%d%d", &x, &y);
p = 0;
while (!(x & 1))
{
x >>= 1;
++p;
}
W[p].push_back(x), w[p] += x;
V[p].push_back(y);
len = max(len, p);
}
for (int i = 0; i <= len; ++i)
{
for (unsigned j = 0; j < W[i].size(); ++j)
{
for (int k = w[i]; k >= W[i][j]; --k)
{
f[i][k] = max(f[i][k], f[i][k - W[i][j]] + V[i][j]);
}
}
}
while (m >> (len + 1)) ++len;
for (int i = 1; i <= len; ++i)
{
w[i] += (w[i - 1] + 1) / 2;//上下取整的转换
for (int j = w[i]; j >= 0; --j)
{
for (int k = 0; k <= j; ++k)
{
f[i][j] = max(f[i][j], f[i][j - k] +
f[i - 1][min(w[i - 1], (k << 1) | ((m >> (i - 1)) & 1))]);
}
}
}
printf("%d\n", f[len][1]);
scanf("%d%d", &n, &m);
memset(W, 0, sizeof(W));
memset(V, 0, sizeof(V));
memset(w, 0, sizeof(w));
memset(f, 0, sizeof(f));
}
}
}
int main()
{
Primary::main();
return 0;
}
```