背包问题
$$ 动态规划 \begin{cases} 状态表示 \begin{cases} 集合 \begin{cases} 选法 \\ \\ 条件 \\ \end{cases} \\ 属性 \quad Max、Min、数量 \\ \end{cases} \\ 状态计算 —— 集合划分(不重、不漏)\\ \end{cases} $$
01背包问题 —— 模板题 AcWing 2. 01背包问题
$$ 01背包 \begin{cases} 状态表示 f[i][j] \begin{cases} 集合 \begin{cases} 所有选法 \\ \\ 条件 \begin{cases} 只从前i个物品中选 \\ 总体积≤j \\ \end{cases} \\ \end{cases} \\ 属性 \quad Max \\ \end{cases} \\ 状态计算 —— 集合划分 \quad f[i - 1][j](不选i) 和 f[i - 1][j - V[i]] + W[i](选i)\\ (体积V、价值W) \end{cases} $$
// 二维01背包
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 = 0; 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;
}
// 一维01背包
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 -- ) // 如果正序遍历,上一轮的结果就会提前被覆盖,和状态转移方程一致
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
return 0;
}
完全背包问题 —— 模板题 AcWing 3. 完全背包问题
$$ 完全背包 \begin{cases} 状态表示 f[i][j] \begin{cases} 集合 \begin{cases} 所有选法 \\ \\ 条件 \begin{cases} 只从前i个物品中选 \\ 总体积≤j \\ \end{cases} \\ \end{cases} \\ 属性 \quad Max \\ \end{cases} \\ 状态计算 —— 集合划分 \quad f[i,j] = f[i-1,j-v[i]*k]+w[i]*k(选了k个,k=0,1,2,3…)\\ (体积V、价值W) \end{cases} $$
二维状态转移方程 f[i][j] = f[i - 1][j - v[i] * k] + w[i] * k;
1式 f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2 * v] + 2 * w, …);
2式 f[i][j - v] = max( f[i - 1][j - v] , f[i - 1][j - 2 * v] + w , …);
由2式,斜体部分 = f[i][j - v] + w
由此,可推得:一维状态转移方程 f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
// 二维完全背包
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 = 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];
return 0;
}
// 一维完全背包
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 = v[i]; j <= m; j ++ ) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m];
return 0;
}
多重背包问题 —— 模板题 AcWing 4. 多重背包问题、AcWing 5. 多重背包问题 II
$$ 完全背包 \begin{cases} 状态表示 f[i][j] \begin{cases} 集合 \begin{cases} 所有选法 \\ \\ 条件 \begin{cases} 只从前i个物品中选 \\ 总体积≤j \\ \end{cases} \\ \end{cases} \\ 属性 \quad Max \\ \end{cases} \\ 状态计算 —— 集合划分 \quad \\ (体积V、价值W、数量S) \end{cases} $$
首先,尝试能否使用类似完全背包的方法对状态转移方程进行化简
f[i, j] = max(f[i - 1, j], f[i - 1, j - v] + w, f[i - 1, j - 2v] + 2w, … , f[i - 1, j - sv] + sw)
f[i, j - v] = max( f[i - 1, j - v] , f[i - 1, j - 2v] + w , … , f[i - 1, j - sv] + (s - 1)w, f[i - 1, j - (s + 1)v] + sw)
已知f[i, j - v],但是无法对f[i, j]的计算方法进行化简,尝试失败
然后,想到使用二进制优化法
将每一种物品的数量s[i]进行分组,(如果s[i] = 31+19 = 50)分成1, 2, 4, 8, 16, 19
将其转化为01背包问题,对于每一组的物品,选或不选,最终可以且仅可以凑出0 - 50中所有的数
// 朴素二维多重背包
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i ++ ) { // 第i种物品
for (int j = 0; j <= m; j ++ ) { // 不超过j个单位体积
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) { // 每种物品选择k个
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][m];
return 0;
}
// 二进制优化一维多重背包
#include <iostream>
using namespace std;
const int N = 25000, M = 2005;
int n, m;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> m;
int cnt = 0;
int vv, ww, ss;
for (int i = 1; i <= n; i ++ ) {
cin >> vv >> ww >> ss;
int k = 1;
while (k <= ss) {
cnt ++ ;
v[cnt] = vv * k;
w[cnt] = ww * k;
ss -= k;
k <<= 1;
}
if (ss > 0) {
cnt ++ ;
v[cnt] = vv * ss;
w[cnt] = ww * ss;
}
}
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];
return 0;
}
分组背包问题 —— 模板题 AcWing 9. 分组背包问题
#include <iostream>
using namespace std;
const int N = 105;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> s[i];
for (int j = 1; j <= s[i]; j ++ )
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++ ) {
for (int j = m; j >= 0; j -- ) {
for (int k = 1; k <= s[i]; k ++ ) {
if (v[i][k] <= j) {
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
}
cout << f[m];
return 0;
}