背包问题 3
归纳状态表示:
- 体积至多是 j:
f[0] = f[1] = ... = 0 && 更新时V >= 0.
- 体积恰好是 j:
f[0] = 0 && f[1] = f[2] = ... = +INF && 更新时V >= 0.
- 体积最少是 j:
f[0] = 0 && f[1] = f[2] = ... = +INF.
- 1020 潜水员
1020 潜水员
动态规划:
- 状态表示:
f[i,j,k]
- 集合: 所有从前i个物品中选，且氧气含量至少是j，氮气含量至少是k 的所有选法
- 属性: min
- 状态计算:
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | #include <cstring>
#include <iostream>
using namespace std;
const int N = 22, M = 80;
int n, m, K;
int f[N][M];
int main()
{
cin >> n >> m >> K;
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
while (K -- )
{
int v1, v2, w;
cin >> v1 >> v2 >> w;
// (1) 从i-1层转移而来，所以是从大到小循环
// (2) 当 i-v1 < 0 OR j-v2 <0 时, 仍成立, 等价f[0][0].
// 注意: 对应于 "体积最少是 j" 的情况!!!
for (int i = n; i >= 0; i -- )
for (int j = m; j >= 0; j -- )
f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
}
cout << f[n][m] << endl;
return 0;
}
|
12 背包问题求具体方案
以01背包为例:
| Text Only |
|---|
| f[i,j] = max ( f[i-1][j], f[i-1][j-Vi] + Wi )
本质上我只需要追踪 f[i,j] 是由这二者中的哪一个转移而来
- f[i-1][j] != f[i-1][j-Vi] + Wi: 选等于 f[i,j] 者
- f[i-1][j] == f[i-1][j-Vi] + Wi: 任选一个
|
题面:
有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 \(1…N\)
注意需要“字典序最小”
比如从前往后看, 对于1号物品
- 只能选择: 必须选
- 只能不选择: 必须不选
- 可选可不选: 一定要选 ⚠️
由于正常循环, f[n,m] 是 “由n-1推的” , 因此需要逆向循环 !!! (有点绕)
[!tip] 背包问题进行方案选择 <-> 追踪转移
- 先完成所有DP计算：首先，完整地计算出整个 f 数组，f[total_n][total_v] 会得到最终的最大价值
- 再反向推导方案：根据计算好的 f 数组，从 f[total_n][total_v] 开始，一步步反推，判断每个物品当初是否被选中
标准的0/1背包问题，如果只要求输出任意一个最优方案，我们可以从 i=N 向 i=1 反向推导
但是，题目要求 字典序最小。这意味着，如果同样能达到最大价值，我们应优先选择编号小的物品。例如，方案 {2, 5} 和 {3, 4} 价值相同，我们必须选择 {2, 5}
- 从
N 到 1 反向推导，会优先对编号大的物品做决策，这和字典序的要求是相反的。
- 为了优先对编号小的物品做决策，我们必须 正向 推导路径。
而正向推导路径，又需要我们预先知道“如果我当前选了物品 i，那么用剩下 i+1...N 的物品能否填满剩余容量并达到最优”
这就引出了解决此问题的经典方法：反向DP，正向选路 !!!!!!
[!danger] 反向DP, 正向选路
(1) 状态定义: f[i][j]: “从第 i 件到第 N 件物品中选择，放入容量为 j 的背包中所能获得的最大价值
(2) 状态转移: f[i][j] = max(f[i+1][j], f[i+1][j - v[i]] + w[i])
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e3+10;
vector<int> path;
int v[maxn], w[maxn];
// 从第i件到第N件物品中选择, 占总容量为j -> 获得的最大价值
int f[maxn][maxn];
int total_n, total_w;
int main()
{
cin >> total_n >> total_w;
for (int i=1; i<=total_n; i++) cin >> w[i] >> v[i];
// [反向DP]
for (int i=total_n; i>=1; i--)
{
for (int j=1; j<=total_w; j++)
{
f[i][j] = f[i+1][j];
if (j - w[i] >= 0)
{
f[i][j] = max(f[i][j], f[i+1][j-w[i]] + v[i]);
}
}
}
// for (int i=1; i<=total_n; i++)
// {
// for (int j=1; j<=total_w; j++)
// cout << f[i][j] << " ";
// cout << endl;
// }
// [正向寻路]
// 检查是否应该选择物品 i
// 1. 当前容量必须能装下物品 i
// 2. 选择物品 i 后的总价值等于从当前状态 f[i][current_w] 出发能达到的最大价值
int current_w = total_w;
for (int i=1; i<=total_n; i++)
{
if (current_w >= w[i]) // 条件(1)
{
if (f[i][current_w] == f[i+1][current_w-w[i]] + v[i])
{
path.push_back(i);
current_w -= w[i]; // 更新剩余容量
}
}
}
for (auto i : path) cout << i << " ";
return 0;
}
|
保存路径, 本质上可以使用 dfs的"最短路" 回溯
9 分组背包问题
有 N 组物品和一个容量是 V 的背包
每组物品有若干个，同一组内的物品最多只能选一个
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大
输出最大价值:
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | #include<iostream>
#include<algorithm>
using namespace std;
/*
分组背包:
f[i][j]: 只在前i组物品中选，总体积不超过j的选法 -> 对应的总价值max
递推式:
f[i][j] = max (
f[i-1][j],
...
f[i-1][j-v[i,k]] + w[i,k]
)
遍历考察第i组选择第k个物件的情况
*/
const int maxn = 110;
int v[maxn][maxn], w[maxn][maxn];
int s[maxn];
int f[maxn][maxn];
int N, V;
int main()
{
cin >> N >> V;
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];
}
// // 初始化f[0][j]为0
// for (int j=0; j<=V; j++) f[0][j] = 0;
for (int i=1; i<=N; i++)
{
for (int j=0; j<=V; j++)
{
f[i][j] = f[i-1][j];
for (int k=1; k<=s[i]; k++)
{
if (j - v[i][k] >= 0) // 注意这里的下标是v[i][k]
f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]);
}
}
}
cout << f[N][V] << endl;
return 0;
}
|
1013 机器分配
总公司拥有 M 台 相同 的高效设备，准备分给下属的 N 个分公司
各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关
问：如何分配这M台设备才能使国家得到的盈利最大？
求出最大盈利值
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M
转化思路: "组内互斥"
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 | #include <iostream>
using namespace std;
const int N = 20;
int n, m;
int w[N][N];
int f[N][N];
int path[N], cnt;
/*
"动态规划求状态转移路径" 等价于在 "拓扑图中找最短路径"
可以直接沿用 "最短路" 输出路径的方法就可以找出 "状态的转移"
*/
void dfs(int i, int j)
{
if (!i) return;
//寻找当前状态f[i][j]是从上述哪一个f[i-1][k]状态转移过来的
for (int a = 0; a <= j; ++ a)
{
if (f[i - 1][j - a] + w[i][a] == f[i][j])
{
path[cnt ++ ] = a;
dfs(i - 1, j - a);
return;
}
}
}
int main()
{
//input
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
cin >> w[i][j];
//dp
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
for (int k = 0; k <= j; ++ k)
f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
cout << f[n][m] << endl;
//find path
dfs(n, m);
for (int i = cnt - 1, id = 1; i >= 0; -- i, ++ id)
cout << id << " " << path[i] << endl;
return 0;
}
|
489 金明的预算方案
思路: 主+副 = 一个组
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 | #include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
const int N = 60, M = 32010;
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++ )
{
int v, p, q;
cin >> v >> p >> q;
p *= v;
if (!q) master[i] = {v, p};
else servent[q].push_back({v, p});
}
for (int i = 1; i <= n; i ++ )
for (int u = m; u >= 0; u -- )
{
/*
二进制枚举, 有点牛b:
servent[i].size() 取值范围为[0, 2]，j的取值范围[0, 3]， k的取值范围[0,1]
- 当 j = 0 时：k 无论为0还是1，都不取
- 当 j = 1 时：k = 0 取，k = 1 不取
- 当 j = 2 时：k = 0 不取，k = 1 取
- 当 j = 3 时：k = 0 || k = 1 都取
分别对应四种互斥情况
*/
for (int j = 0; j < 1 << servent[i].size(); j ++ )
{
int v = master[i].v, w = master[i].w;
for (int k = 0; k < servent[i].size(); k ++ )
if (j >> k & 1)
{
v += servent[i][k].v;
w += servent[i][k].w;
}
if (u >= v) f[u] = max(f[u], f[u - v] + w);
}
}
cout << f[m] << endl;
return 0;
}
|
426 开心的金明
简单的01背包
将原问题做如下转化
- 总钱数相当于背包总容量
- 每件物品的价格相当于体积
- 每件物品的价格乘以重要度相当于价值
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | #include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int n, m;
int f[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
w *= v;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
|
