每日OJ题_其它背包问题①_力扣474. 一和零（二维费用01背包）

力扣474. 一和零

解析代码

代码优化

力扣474. 一和零

474. 一和零

难度中等

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {}
};

解析代码

先看能不能将问题转化成我们熟悉的题型。

在一些物品中挑选一些出来，然后在满足某个限定条件下，解决一些问题，大概率是背包模型，由于每一个物品都只有 1 个，因此是一个01 背包问题。但是发现这一道题里面有两个限制条件。因此是一个二维费用的 01 背包问题。那么定义状态表示的时候，创建一个三维 dp 表，把第二个限制条件加上即可。

二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（例：背包容量，问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。）

故：对于01背包问题、完全背包问题和多重背包问题的方法都完全可以使用，只不过增加一个代价。

状态表示：dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ，字符 1 的个数不超过 k ，所有的选法中，最大的长度。

状态转移方程：

线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。为了方便叙述，记第 i 个字符中，字符 0 的个数为 a ，字符 1 的个数为 b ：

不选第 i 个字符串：相当于就是去前 i - 1 个字符串中挑选，并且字符 0 的个数不超过 j ，字符 1 的个数不超过 k 。此时的最大长度为 dp[i][j][k] = dp[i - 1] [j][k] 。
选择第 i 个字符串：那么接下来仅需在前 i - 1 个字符串里面，挑选出来字符 0 的个数不超过 j - a ，字符 1 的个数不超过 k - b 的最长长度，然后在这个长度后面加上字符串 i 即可。此时 dp[i][j][k] = dp[i - 1][j - a][k - b] + 1 。但是这种状态不⼀定存在，因此需要特判⼀下。

综上，状态转移方程为：dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a] [k - b] + 1) ;

初始化： 每一维多开一个空间方便初始化，当第一维i为0 即没有字符串的时候，没有长度，因此初始化为 0 即可。

填表顺序： 保证第一维i 从小到大即可。

返回值： 根据状态表示，返回 dp[len][m][n] ，其中 len 表示字符串数组的长度。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,// 字符 1 的个数不超过 k ，所有的选法中，最大的长度int len = strs.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));for(int i = 1; i <= len; ++i){int a = 0, b = 0;for(auto& e : strs[i - 1]) // 统计0和1的个数{if(e == '0')++a;    else++b;}for(int j = 0; j <= m; ++j){for(int k = 0; k <= n; ++k){if(j >= a && k >= b)dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + 1) ;elsedp[i][j][k] = dp[i - 1][j][k];}}}return dp[len][m][n];}
};

代码优化

所有的背包问题，都可以进行空间上的优化。对于二维费用的 01 背包问题，优化还是和之前的01背包类似，删掉第一维，然后修改其他维度的遍历顺序：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,// 字符 1 的个数不超过 k ，所有的选法中，最大的长度int len = strs.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(int i = 1; i <= len; ++i){int a = 0, b = 0;for(auto& e : strs[i - 1]) // 统计0和1的个数{if(e == '0')++a;    else++b;}for(int j = m; j >= 0; --j){for(int k = n; k >= 0; --k){if(j >= a && k >= b)dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1) ;elsedp[j][k] = dp[j][k];}}}return dp[m][n];}
};