考点
思路
二维01背包的精髓题，必须搞懂
暴力DP
每个字符串都有若干个0和1，每个字符串选或不选两种状态
总的01个数相同的情况下，选字符串个数最大的，这就是经典的01背包，很容易写出下面的三维DP
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
| class Solution {
public:
int findMaxForm(vector<string>& strs, int M, int N) {
int c0[605], c1[605];
memset(c0, 0, sizeof(c0)), memset(c1, 0, sizeof(c1));
for (int i = 0; i < strs.size(); ++i) {
for (int j = 0; j < strs[i].size(); ++j) {
if (strs[i][j] == '0')
c0[i]++;
else
c1[i]++;
}
}
int f[605][105][105];
memset(f, 0xcf, sizeof(f));
f[0][0][0]=0;
int n = strs.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= M; ++j) {
for (int k = 0; k <= N; ++k) {
if(f[i][j][k] == 0xcfcfcfcf) continue;
f[i + 1][j][k] = max(f[i + 1][j][k], f[i][j][k]);
if (j + c0[i] <= M && k + c1[i] <= N)
f[i + 1][j + c0[i]][k + c1[i]] =
max(f[i + 1][j + c0[i]][k + c1[i]], f[i][j][k] + 1);
}
}
}
int ans = 0;
for (int j = 0; j <= M; ++j) {
for (int k = 0; k <= N; ++k) {
ans = max(ans, f[n][j][k]);
}
}
return ans;
}
};
|
正序逆序问题
第一维可以滚动数组去掉，但是这里j和k都必须逆序
尽管j把k隔离开了，但是可以发现在c0 = 0的情况下，状态转移方程退化为
1
| f[j + 0][k + c1] = max(f[j + 0][k + c1], f[j][k] + 1);
|
实际上就是在同一层做01背包，所以k也必须进行倒序
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
| class Solution {
public:
int findMaxForm(vector<string>& strs, int M, int N) {
int f[105][105], n = strs.size();
memset(f, 0xcf, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < n; ++i) {
int c0 = 0, c1 = 0;
for (char chr : strs[i]) chr == '0' ? c0++ : c1++;
for (int j = M - c0; j >= 0; --j) {
for (int k = N - c1; k >=0 ; --k) {
if (f[j][k] < 0) continue;
f[j + c0][k + c1] = max(f[j + c0][k + c1], f[j][k] + 1);
}
}
}
int ans = 0;
for (int j = 0; j <= M; ++j) {
for (int k = 0; k <= N; ++k) {
ans = max(ans, f[j][k]);
}
}
return ans;
}
};
|
当然如果你不信的话，单独把c0 == 0这一层剥开就行了，发现正序也能AC
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
| class Solution {
public:
int findMaxForm(vector<string>& strs, int M, int N) {
int f[105][105], n = strs.size();
memset(f, 0xcf, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < n; ++i) {
int c0 = 0, c1 = 0;
for (char chr : strs[i])
chr == '0' ? c0++ : c1++;
for (int j = M - c0; j >= 0; --j) {
if (c0) {
for (int k = 0; k <= N - c1; ++k) {
if (f[j][k] < 0)
continue;
f[j + c0][k + c1] = max(f[j + c0][k + c1], f[j][k] + 1);
}
} else {
for (int k = N - c1; k >= 0; --k) {
if (f[j][k] < 0)
continue;
f[j + c0][k + c1] = max(f[j + c0][k + c1], f[j][k] + 1);
}
}
}
}
int ans = 0;
for (int j = 0; j <= M; ++j) {
for (int k = 0; k <= N; ++k) {
ans = max(ans, f[j][k]);
}
}
return ans;
}
};
|
背包容量从“刚好”变成“小于等于”
先考虑经典的背包问题
迄今为止，我们定义的背包容量都是“刚好”，这样好想也好写
即f[i][j]为前i个物品刚好达到容量j，这也是为什么最后需要遍历所有的f[n][0 ~ m]来找极值，因为不一定能装满
现在改成f[i][j]为前i个物品的容量小于等于j，情况变成如下：
1
2
3
| 初始值, memset(f, 0 ,sizeof(f)), f[0][0 ~ m] = 0
f[i][j] = max(f[i-1][j], f[i-1][j - w[i]] + v[i])
答案, f[n][m]
|
对比我们经典的模型，发现只有初值和结果不同而已，方程竟然是没变的：
1
2
3
| 初始值, memset(f, 0xcf ,sizeof(f)), f[0][0] = 0
f[i][j] = max(f[i-1][j], f[i-1][j - w[i]] + v[i])
答案, max(f[n][0 ~ m])
|
很容易理解，举个例子，和 <= 5，但当前物品重量为3，两边同时减去3，得到和 - 3 <= 5 - 3，即和 <= 2
如果实在觉得荒谬，我也做了数学推导，可以看图：
那么这题也可以用新的定义压缩代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int findMaxForm(vector<string>& strs, int M, int N) {
int f[105][105], n = strs.size();
memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
int c0 = 0, c1 = 0;
for (char chr : strs[i]) chr == '0' ? c0++ : c1++;
for (int j = M - c0; j >= 0; --j) {
for (int k = N - c1; k >= 0; --k) {
f[j + c0][k + c1] = max(f[j + c0][k + c1], f[j][k] + 1);
}
}
}
return f[M][N];
}
};
|