從一個字串陣列中找出由A個0和B個1組成的最長子集的長度

Input –  arr = {"101", "0", "101", "0", "1"}, A = 2, B = 1

Input –  arr = {"0", "101", "0", "1"}, A = 3, B = 3

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int 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 Code
int 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;
}

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int 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;
}