力扣：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

二、问题分析

  题目要求找到strs字符串数组的最大子集，而且该子集中最多有m个“0”和n个“1”，也就是说从strs数组选出部分字符串，使得这些字符串中所有“0”最多有m个，“1”最多有n个。

这就符合动态规划0-1背包理论，只是这是背包有两个维度，一个是m，另一个是n。

• 确定dp数组及下标的含义：dp[ i i i][ j j j]：最多有 i i i个0和 j j j个1的strs的最大子集的元素数量
• 确定递推公式：当前字符串有zeroNum个0、oneNum个1，dp[ i i i][ j j j]可以从dp[ i i i-zeroNum][ j j j-oneNum]推导出来，所以递推公式：dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
• 初始化dp数组：dp数组初始化为0即可
• 确定遍历顺序：遍历顺序逻辑与0-1背包是一样的，遍历物品的for循环放在外层，遍历背包的for循环放在内层，且内层for循环使用倒叙遍历。
  

  
  

三、代码实现

// 编程软件：VS2019
// 参考书籍：代码随想录

#include
#include
#include
#include
using namespace std;

// 动态规划
int findMaxForm(vector<string>& strs, int m, int n) {
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	// 遍历物品
	for (string str : strs) { 
		int zeroNum = 0, oneNum = 0; // 记录当前字符串中“0”和“1”的个数
		// 遍历当前字符串，计算字符串中“0”和“1”的个数
		for (char c : str) { 
			if (c == '0') zeroNum++;
			else oneNum ++ ;
		}
		// 遍历背包容量且从后向前遍历，这里二个for顺序颠倒也是可以的
		for (int i = m; i >= zeroNum; i--) { 
			for (int j = n; j >= oneNum; j--) {
				dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum]+1);
			}
		}
	}
	return dp[m][n];
}

int main() {
	vector<string>nums = {"10","0001","111001","1","0"};
	int m = 5, n = 3;
	cout << findMaxForm(nums, m, n);
}
// 结果：4

四、小结

  本题用0-1背包实现起来很简单，但是可能看到题目有两个最大背包容量，就会去想其他背包理论吧。

其实不然，只是将背包看成有二个维度的背包，然后再个0-1背包理论逻辑结合分析，就能很快写出代码了。