算法 | 动态规划背包模型 - B
通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（分治）的方式去解决：动态规划 (Dynamic Programming, DP)
多重背包模型
例题
来源：AcWing04 - 多重背包问题 I - https://www.acwing.com/problem/content/4/
有 $N$ 种物品和一个容量是 $V$ 的背包。
第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。
接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
$0 \lt N, V \le 100$
$0 \lt v_i, w_i, s_i \le 100$
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10
分析 & 代码
暴力解法
多重背包和完全背包的区别就是每一种物品取得数量有一个上限 $s_i$，那么可以直接用完全背包的暴力代码，在第三层循环限制下 $ k\leq s_i$ 就好了。
- 时间复杂度：$O(N\cdot V^2)$ (最坏情况)
- 空间复杂度：$O(V)$
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE = 1010;
int N, V;
int v[SIZE], w[SIZE], s[SIZE];
int dp[SIZE];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= N; i++)
for (int j = V; j >= v[i]; j--)
for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
cout << dp[V] << endl;
return 0;
}二进制优化
暴力解法中第三层循环从 $1$ 遍历到了 $s_i$，当数据过大时，三层循环会超时，我们需要优化这个遍历过程。先看下面的例子：
一个数 $200$，我们可以将其拆为 $1,2,4,8,16,32,64,73$ 这 $8$ 个数，那么通过这 $8$ 个数的不同取法，我们可以拼凑出 $0\sim 200$ 的所有情况。因为 $1$ 可拼凑 $1$，$1,2$ 可拼凑 $1,2,3$，$1,2,4$ 可拼凑 $1,2,3,4,5,6,7$，以此类推即可得证。
那么对于任意一个数 $N$，我们都能找到一组数 $2^0,2^1,2^2,\cdots,2^k,N-2^{k+1}+1$，通过这一组数的不同取法拼凑出 $0\sim N$ 的所有数。
通过这种思想，我们改变第三层循环的方式，不去一个一个取物品，而是将物品每 $1$ 个、$2$ 个、$4$ 个……打包，然后分析打包好的包裹的不同取法，即变成了 01-背包问题。
- 时间复杂度：$O(N\cdot\log{S}\cdot V)$
- 空间复杂度：$O(V)$ (已包含空间优化)
#include <iostream>
#include <algorithm>
using namespace std;
// 需要注意各个数组的大小
const int SIZE_NlogS = 25000, SIZE_V = 2010;
int N, V, idx;
int v[SIZE_NlogS], w[SIZE_NlogS];
int dp[SIZE_V];
int main()
{
cin >> N >> V;
// 物品读入
for (int i = 1; i <= N; i++)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
// 物品打包
while (k <= s)
{
v[++idx] = a * k;
w[idx] = b * k;
s -= k;
k *= 2;
}
if (s)
{
v[++idx] = a * s;
w[idx] = b * s;
}
}
// 01-背包问题
for (int i = 1; i <= idx; i++)
for (int j = V; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
return 0;
}单调队列优化
对于完全背包问题，我们每轮能够取到的数量 $k$ 没有限制，最大均可取到 $\lfloor\frac{j}{v_i}\rfloor$. 由于这个性质，从 $dp(i,j-v_i)$ 到 $dp(i,j)$ 实际上只新增了最左边的 $dp(i-1,j)$ 一项，就可以得到以下的式子，将第三层循环优化掉：
$$ \begin{align} dp(i,j)&=\max\left\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots,dp(i-1,j-kv_i)+k w_i\right\}\\ dp(i,j-v_i)&=\max\left\{dp(i-1,j-v_i),\cdots,dp(i-1,j-kv_i)+(k-1)w_i\right\}\\ &\Rightarrow dp(i,j)=\max\left\{dp(i-1,j),dp(i,j-v_i)+w_i\right\} \end{align} $$
但对于多重背包模型，我们每轮能够取到的数量有上界 $s_i$，那么式子就变成了：
$$ \begin{align} dp(i,j)&=\max\left\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots,dp(i-1,j-s_iv_i)+s_iw_i\right\}\\ dp(i,j-v_i)&=\max\left\{dp(i-1,j-v_i),\cdots,dp(i-1,j-(s_i+1)v_i)+s_iw_i\right\}\\ \end{align} $$
此时我们会发现，从 $dp(i,j-v_i)$ 到 $dp(i,j)$，不仅左边新增了一项 $dp(i-1,j)$，而且右边少了一项 $dp(i-1,j-(s_i+1)\times v_i)$，因此完全背包的递推式无法在这里使用。
不过，这个式子满足滑动窗口的性质，我们相当于每次都维护一个长度为 $s_i$ 的滑动窗口，求窗口内的最大值。因此可以使用单调递减队列来维护窗口中的最大值。
其中，单调递减队列储存 $1\sim V$ 的下标值，队头代表着滑动窗口内对应值最大的下标值。
我们可以发现 $dp(i,j)$ 比 $dp(i,j-v_i)$ 整体多了 $w_i$，即对于不同大小的 $j$，$dp(i,j)$ 存在整体偏移量 $n\cdot w_i$，如果我们要用单调队列维护最大值，必须消除这个偏移量的干扰。我们使用的方法是将每一项统一为下面的格式：
$$ \dots\dots,\;\;dp(i,r+3v)-3w,\;\;dp(i,r+2v)-2w,\;\;dp(i,r+v)-w,\;\;dp(i,r) $$
即单调队列比较时使用：$dp(i-1,x)-(x-r)/v_i\times w_i$
- 时间复杂度：$O(N\cdot V)$
- 空间复杂度：$O(V)$ (已包含空间优化)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int main()
{
int N, V;
cin >> N >> V;
vector<int> v(N + 10), w(N + 10), s(N + 10);
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i] >> s[i];
vector<int> dp(V + 10), lst(V + 10), que(V + 10);
for (int i = 1; i <= N; i++)
{
lst = dp;
for (int r = 0; r < v[i]; r++)
{
int hh = 0, tt = -1;
for (int k = r; k <= V; k += v[i])
{
if (hh <= tt && que[hh] < k - s[i] * v[i])
++hh;
while (hh <= tt && lst[que[tt]] - (que[tt] - r) / v[i] * w[i] <= lst[k] - (k - r) / v[i] * w[i])
--tt;
if (hh <= tt)
dp[k] = max(dp[k], lst[que[hh]] - (que[hh] - k) / v[i] * w[i]);
que[++tt] = k;
}
}
}
cout << dp[V] << endl;
return 0;
}分组背包问题
例题
来源：AcWing09 - 分组背包问题 - https://www.acwing.com/problem/content/9/
有 $N$ 组物品和一个容量是 $V$ 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 $N，V$，用空格隔开，分别表示物品组数和背包容量。
接下来有 $N$ 组数据：
- 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
- 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}, w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
$0 \lt N, V \le 100$
$0 \lt S_i \le 100$
$0 \lt v_{ij}, w_{ij} \le 100$
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8
分析
实际仍然能当作“01-背包问题”来看，只不过“01-背包问题”的每一个物品变成了一组物品，不过我们只用遍历这一组，求到这一组物品的最优情况即可。
- 时间复杂度：$O(V\cdot\sum{S})$
- 空间复杂度：$O(V)$ (已包含空间优化)
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 110;
int N, V;
int v[SIZE][SIZE], w[SIZE][SIZE], S[SIZE];
int dp[SIZE];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
{
cin >> S[i];
for (int j = 0; j < S[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 0; i <= N; i++)
for (int j = V; j >= 0; j--)
for (int k = 0; k < S[i]; k++)
if (v[i][k] <= j)
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
cout << dp[V] << endl;
return 0;
}混合背包问题
例题
有 $N$ 种物品和一个容量是 $V$ 的背包。
物品一共有三类：
- 第一类物品只能用 $1$ 次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 $s_i$ 次（多重背包）；
每种体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，$N$，$V$，用空格隔开，分别表示物品种数和背包容积。
接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。
- $s_i=−1$ 表示第 $i$ 种物品只能用 $1$ 次；
- $s_i=0$ 表示第 $i$ 种物品可以用无限次；
- $s_i>0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；
输出格式
输出一个整数，表示最大价值。
数据范围
$0<N,V≤1000$
$0<vi,wi≤1000$
$−1≤s_i≤1000$
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例
8
分析
对于混合背包问题，我们的处理方式其实就是对于每一个物品对应的背包模型，使用对应的处理方式。
对于完全背包，我们直接用完全背包的计算方式即可。对于多重背包问题，我们使用二进制优化方式转化为 0-1 背包问题，与 0-1 背包一起统一处理即可。
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve()
{
int N, V;
cin >> N >> V;
vector<int> dp(V + 10);
for (int i = 1; i <= N; i++)
{
int v, w, s;
cin >> v >> w >> s;
if (s == 0) // 完全背包
{
for (int j = v; j <= V; j++)
dp[j] = max(dp[j], dp[j - v] + w);
}
else // 0-1背包 和 多重背包
{
s = abs(s); // 一律当多重背包转化成0-1背包
vector<int> vv, ww;
int k = 1;
while (k <= s)
{
vv.push_back(v * k);
ww.push_back(w * k);
s -= k;
k *= 2;
}
if (s)
{
vv.push_back(v * s);
ww.push_back(w * s);
}
for (int j = 0; j < vv.size(); j++)
for (int k = V; k >= vv[j]; k--)
dp[k] = max(dp[k], dp[k - vv[j]] + ww[j]);
}
}
cout << dp[V] << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}本文采用 CC BY-NC-SA 4.0 许可，本文 Markdown 源码：Haotian-BiJi