由于每个物体只有 种可能的状态(取与不取),正如二进制中的1100 ,这类问题便被称为“0-1 背包问题”

0-1背包

由于每个物体只有 种可能的状态(取与不取),正如二进制中的1100 ,这类问题便被称为“0-1 背包问题”

设 DP 状态fi,jf_{i,j}为在只能放前ii个物品的情况下,容量为jj 的背包所能达到的最大总价值。

假设当前已经处理好了前i1i-1个物品的所有状态,那么对于第ii个物品,当其不放入背包时,背包的剩余容量不变,背包中物品的总价值也不变,故这种情况的最大价值为fi1,jf_{i-1,j};当其放入背包时,背包的剩余容量会减小 ,背包中物品的总价值会增大 ,故这种情况的最大价值为fi1,jw[i]+v[i]f_{i -1,j-w[i]} + v[i]

故我们得到状态方程:$$f_{i, j}=\max \left(f_{i-1, j}, f_{i-1, j-w_{i}}+v_{i}\right)$$

1
2
3
4
5
6
\\对应代码
for (int i = 1; i <= n; i++)
for (int j = 1; j <=W; j++){
f[i][j] = (i == j ? 0 : f[i - 1][j])
if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i])
}

但我们可以得出,fif_{i} 计算时,实际上它在考察fi1f_{i-1}的值,并选取合适的值再进行填充,所以我们可以采用覆盖的方法直接再一维数组上进行操作,得出状态方程 : fj=max(fj, fjw[i]+v[i])f_{j} = max(f_{j},\ f_{j-w[i]} + v[i])

但是需要特别注意的是,我们把f[i]去掉之后,代码变成了f[j] = max(f[j], f[j - w[i]] + v[i]),其中f[j-w[i]]是在数组的后面的,如果顺序从1到W枚举,则会不断得改变,所以应当从后往前枚举. 复杂度为O(nW)O(n W)

1
2
3
for (int i = 1; i <= n; i++)
for (int l = W; l >= w[i]; l--)
f[l] = max(f[l], f[l - w[i]] + v[i]);

例题: https://www.luogu.com.cn/problem/P2871

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3450;
int v[maxn], w[maxn], f[maxn];
int main(){
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> w[i] >> v[i];
for (int i = 0; i < n; i++)
for (int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m];
}

完全背包

朴素思想,从01背包问题继承下来,我们考察每一个物品时,另外增加一层分别取0i0 - i个物品,可以得出复杂度为O(n3)O(n^{3})

1
2
3
4
for (int i = 0; i < n; i++) \\对应代码
for (int j = W; j >= w[i]; j--)
for (int k = 0; k <= W / w[i]; k++)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);

给出一个优化,当我们考察fi,jf_{i,j}时,总会是考察fi1,jf_{i-1,j}的状态能否到达fi,jf_{i,j}fi,jw[i]f_{i,j-w[i]}能否到达的最值,这里时重点需要理解清楚可在二维数组上推演一下便可得出状态方程 $$f_{i, j}=\max \left(f_{i-1, j}, f_{i, j-w_{i}}+v_{i}\right)$$

参考01背包我们同样可以再进一步优化到一维数组$$f_{ j}=\max \left(f_{ j}, f_{ j-w[i]}+v_{i}\right)$$

压缩一下结果发现时一样的?? NONONO.我们考察01背包更新数组的时候,数据采用的是上一条相同位置和jw[i]j-w[i]的位置的数据,他们都是相对于jj 靠前的,所以我们采用了逆序遍历.对于本问题,我们采用的数据是上一条相同位置和本条jw[i]j-w[i] 的数据,是递推过来的,所以我们应当顺序遍历,得到代码如下.其中复杂度为O(nW)O(n W)

1
2
3
for (int i = 1; i <= n; i++)
for (int l = w[i]; l <= W; l++)
f[j] = max(f[j], f[j - w[i]] + v[i]);

例题 : https://www.luogu.com.cn/problem/P1616

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;
const int maxn = 1e5 + 10;
int t, m;
int w[maxn], v[maxn], f[maxn];
int main(){
cin >> t >> m;
for (int i = 1; i <= m; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= m; i++)
for (int j = w[i]; j <= t; j++)
f[j] = max(f[j], f[j - w[i]]+ v[i]);
cout << f[t];
return 0;
}

多重背包

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种i物品 y 有 kik_{i}个,而非 11 个。

一个很朴素的想法就是:把“每种物品选 kik_{i}次”等价转换为“有 kik_{i}个相同的物品,每个物品选一次”。这样就转换成了一个 0-1 背包模型,套用上文所述的方法就可已解决。状态转移方程如下:
\begin{equation}f_{i, j}=\max\left(f_{i-1, j-k \times w_{i}}+v_{i} \times k\right)\end{equation}

同样我们给出一维优化, 状态方程:

fj=max(fj, fjw[i]+v[i])f_{j} = max(f_{j},\ f_{j-w[i]} + v[i])

不过在这里我们需要增加一层次数的循环,代码如下.复杂度O(nWki)O(n W\sum k_{i})

1
2
3
4
for (int i = 1; i <= n; i++)
for (int k = 1; k <= m[i]; k++)
for (int j = W; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);

例题 :https://www.acwing.com/problem/content/4/

例题 :https://www.luogu.com.cn/problem/P1776

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
const int maxn = 1e5 + 10;
using namespace std;
int n, W;
int m[maxn], w[maxn], v[maxn], f[maxn];
int main() {
cin >> n >> W;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i] >> m[i];
for (int i = 1; i <= n; i++)
for (int k = 1; k <= m[i]; k++)
for (int j = W; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[W];
return 0;
}

对于洛谷那道题则会超时(https://www.luogu.com.cn/record/32016907),通过复杂度计算即可得到,所以我们还要继续优化,这里采用二进制优化方法.此方法相当于把重复的加法运算取对数即可大大减少操作次数,则复杂度O(Wlogmi)O(W\sum logm_{i})

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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e7 + 10;
int f[maxn], w[maxn], v[maxn], m[maxn];
int n, W;
int main(){
cin >> n >> W;
int index = 0; \\开始拆分
for (int i = 1; i <= n; i++) {
int cnt = 1, v1, w1, m1;
cin >> v1 >> w1 >> m1;
while (m1 - cnt > 0) {
m1 -= cnt;
w[++index] = cnt * w1;
v[index] = cnt * v1;
cnt *= 2;
}
w[++index] = w1 * m1;
v[index] = v1 * m1;
} \\总物品数为index个

for (int i = 1; i <= index; i++)
for (int j = W; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[W];
return 0;
}

混合背包

混合背包考察的是每一种物品其属性并不是统一 的时候,所以我们对物品进行规划的时候根据属性采用不同的状态方程即可

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; i++) {
if (m[i] == 0) {
for (int j = w[i]; j <= t; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
else {
for (int k = 1; k <= m[i]; k++)
for (int j = t; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}

多维背包

同样是01背包的变形,我们增加一层循环即可,表示对当前的状态下另一个状态的最优解,代码如下

例题 : https://www.luogu.com.cn/problem/P1855

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;

int n, W, T;
int w[maxn], t[maxn], f[maxn][maxn];
int main(){
cin >> n >> W >> T;
for (int i = 1; i <= n; i++)
cin >> w[i] >> t[i];

for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--)
for (int k = T; k >= t[i]; k--)
f[j][k] = max(f[j][k], f[j - w[i]][k - t[i]] + 1);

cout << f[W][T];
return 0;
}

分组背包

例题: https://www.luogu.com.cn/problem/P1757

即物品时分组的,每组只能拿一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;

int n, m, last;
int v[maxn], w[maxn], g[maxn], f[maxn], cnt[maxn], id[maxn][maxn];

int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i] >> g[i];
cnt[g[i]]++;
id[g[i]][cnt[g[i]]] = i;
last = max(g[i], last);
}
for (int k = 1; k <= last; k++) //循环每一组
for (int i = m; i >= 0; i--) //循环背包容量
for (int j = 1; j <= cnt[k]; j++) //循环该组的每一个物品
if (i >= w[id[k][j]])
f[i] = max(f[i], f[i - w[id[k][j]]] + v[id[k][j]]); //像0-1背包一样状态转移
cout << f[m];
return 0;
}

依赖背包


评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

loading...loading... , total visits times