【算法】动态规划 - B
通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(分治)的方式去解决:动态规划 (Dynamic Programming, DP)
Part B
多重背包模型
例题: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
分析
暴力解法
时间复杂度:$O(N\cdot V^2)$ (最坏情况)
多重背包和完全背包的区别就是每一种物品取得数量有一个上限 $s_i$,那么可以直接用完全背包的暴力代码,在第三层循环限制下 $ k\leq s_i$ 就好了。
因此有以下暴力解法:
#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++) // 在此限制 k <= s[i]
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)$
#include <iostream>
#include <algorithm>
using namespace std;
// 需要注意各个数组的大小
const int SIZE_NlogS = 25000, SIZE_V = 2010;
int N, V, cnt;
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)
{
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)
{
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
// 01-背包问题
for (int i = 1; i <= cnt; 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-背包问题的每一个物品变成了一组物品,不过我们只用遍历这一组,求到这一组物品的最大情况并保留即可。
#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;
}