在这个问题中，我们需要找到最多包含a个0和b1的最长子集。我们需要做的就是使用数组元素找到所有可能的子集，并找到包含最多 a 0 和 b1 的最长子集。
在本教程中，首先，我们将学习递归方法来解决问题。之后，我们将使用动态规划的方法来优化代码。
问题陈述 - 我们给出了一个包含 n 个二进制字符串的数组。此外，我们还给出了 a 和 b 整数。我们需要使用给定的二进制字符串创建最长的子集，使其不包含超过 a 0 和 b1。
示例input – arr = {101, 0, 101, 0, 1}, a = 2, b = 1
output – 3

说明最长的子集是{ 0, 0, 1}，包含2个0和1个1。
input – arr = {0, 101, 0, 1}, a = 3, b = 3
output – 3

说明最长的子集是{0, 101, 0, 1}，3个0和3个1。
方法 1在本节中，我们将学习一种使用递归的简单方法。我们将使用数组元素构造所有可能的子集，并找到包含 a 0 和 b 1 的最长子集。
算法步骤 1 - 定义 countzeros() 函数来计算给定二进制字符串中零的总数。
步骤 1.1 - 将“count”变量初始化为零。
步骤 1.2 - 使用 for 循环遍历字符串。
步骤 1.3 - 如果第 i 个索引处的字符为“0”，则将“cnt”的值增加 1。
步骤 1.2 - 返回“cnt”变量的值。
步骤 2 - getmaxsubsetlen() 返回整数值并采用向量 arr、int a、int b 和索引作为参数。
步骤 3 - 定义函数内的基本情况。如果索引等于向量的大小，或者 a 和 b 的值均为零，则返回 0。
第 4 步 - 现在，计算索引处字符串中零的总数。
第 5 步 - 从字符串长度中减去 1 的总数，即可得出 1 的总数。
第 6 步 - 将“第一个”变量初始化为 0。
步骤 7 - 如果 0 和 1 的总数分别小于 a 和 b，则包含当前的二进制字符串。存储 1 + 函数递归调用的返回值。在进行递归调用时，从 a 和 b 中减去 0 和 1。
第 8 步 - 排除当前字符串并将结果值存储在“第二个”变量中。
第 9 步 - 返回第一个和第二个的最大值。
示例#include <bits/stdc++.h>using namespace std;// function to count the number of 0's in a stringint countzeros(string s){ // initialize count variable to 0 int count = 0; // traverse the string for (int i = 0; i < s.size(); i++){ // if the current character is 0, the increment count if (s[i] == '0'){ count++; } } // return count return count;}// recursive function to find the maximum length of a subset of strings according to the given condition.int getmaxsubsetlen(vector<string> arr, int a, int b, int index){ // base case // if all the strings are traversed, or a + b becomes 0 if (index == arr.size() || a + b == 0){ return 0; } // total number of 0's in arr[index] string int zero = countzeros(arr[index]); // total number of 1's in arr[index] string int one = arr[index].size() - zero; // stores the length of the subset, if arr[i] is included. int first = 0; // if the number of 0's and 1's in arr[index] is less than or equal to a and b, respectively, then include the string if (zero <= a && one <= b){ first = 1 + getmaxsubsetlen(arr, a - zero, b - one, index + 1); } // stores the length of the subset, if arr[i] is not included. int second = getmaxsubsetlen(arr, a, b, index + 1); // return the maximum of the first and second return max(first, second);}// driver codeint main(){ vector<string> arr = {101, 0, 101, 0, 1}; int a = 2, b = 1; cout << the maximum length of the subset consisting at most a 0s and b 1s is - <<getmaxsubsetlen(arr, a, b, 0); return 0;}
输出the maximum length of the subset consisting at most a 0s and b 1s is - 3

时间复杂度 - o(2n)，因为我们使用 n 个数组元素找到所有可能的子集。
空间复杂度 - o(1)
方法2我们在本节中对上述方法进行了优化。我们使用动态规划的方法来解决这个问题。它存储前一个状态的结果，以降低问题的时间复杂度。
算法第 1 步 - 定义 countzeros() 函数来计算特定二进制字符串中零的总数，就像我们在上述方法中所做的那样。
步骤 2 - 创建一个大小为 a x b x n 的 3 维向量来存储先前状态的结果。在列表中，当总 0 等于 a 且 1 等于 b 时，我们将在索引“i”处存储子集的长度。此外，将其作为 getmaxsubsetlen() 函数的参数传递。
第 3 步 - 按照我们在上述方法中所做的那样定义基本情况。
步骤 4 - 如果 dptable[a][b][index] 的值大于 0，则表示状态已计算并返回其值。第 5 步 - 计算当前字符串中 0 和 1 的总数。
第 6 步 - 获取包含和排除当前字符串后的结果值。
第 7 步 - 使用 max() 函数获取第一个和第二个的最大值，并将其存储在 dptable[a][b][index] 中后返回
示例#include <bits/stdc++.h>using namespace std;// function to count the number of 0's in a stringint countzeros(string s){ // initialize count variable to 0 int count = 0; // traverse the string for (int i = 0; i < s.size(); i++){ // if the current character is 0, the increment count if (s[i] == '0'){ count++; } } // return count return count;}// recursive function to find the maximum length of a subset of strings according to the given condition.int getmaxsubsetlen(vector<string> array, int a, int b, int index, vector<vector<vector<int>>> &dptable){ // base case if (index == array.size() || a + b == 0){ return 0; } // return if already calculated if (dptable[a][b][index] > 0){ return dptable[a][b][index]; } // total number of 0's in the current string int zero = countzeros(array[index]); // total number of 1's in the current string int one = array[index].size() - zero; // to store the length of the subset can be formed by including the current string int first = 0; // if the total number of 0's and 1's in the current string is less than or equal to a and b, respectively if (zero <= a && one <= b){ first = 1 + getmaxsubsetlen(array, a - zero, b - one, index + 1, dptable); } // to store the length of the subset can be formed by excluding the current string int second = getmaxsubsetlen(array, a, b, index + 1, dptable); // store the maximum of the first and second, and return return dptable[a][b][index] = max(first, second);}int main(){ vector<string> arr = {101, 0, 101, 0, 1}; int a = 2, b = 1; vector<vector<vector<int>>> dptable(a + 1, vector<vector<int>>(b + 1, vector<int>(arr.size() + 1, 0))); cout << the maximum length of the subset consisting at most a 0s and b 1s is - << getmaxsubsetlen(arr, a, b, 0, dptable); return 0;}
输出the maximum length of the subset consisting at most a 0s and b 1s is - 3

时间复杂度 - o(a*b*n)，因为我们需要填充 3d 列表才能获得结果。
空间复杂度 - o(a*b*n)，因为我们使用 3d 列表进行动态规划方法。
以上就是从一个字符串数组中找出由a个0和b个1组成的最长子集的长度的详细内容。