【算法】动态规划 - 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;
}分组背包问题
例题
来源：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;
}