Trouver la longueur du sous-ensemble le plus long composé de A 0 et B 1 à partir d'un tableau de chaînes

Dans ce problème, nous devons trouver le sous-ensemble le plus long contenant au plus des A 0 et des B1. Tout ce que nous avons à faire est de trouver tous les sous-ensembles possibles à l'aide d'éléments de tableau et de trouver le sous-ensemble le plus long contenant au plus A 0 et B1 .

Dans ce tutoriel, nous allons d'abord apprendre la méthode récursive pour résoudre le problème. Après cela, nous utiliserons des méthodes de programmation dynamique pour optimiser le code.

Énoncé du problème - On nous donne un tableau contenant N chaînes binaires. De plus, on nous donne les entiers A et B. Nous devons créer le sous-ensemble le plus long en utilisant la chaîne binaire donnée de telle sorte qu'il ne contienne pas plus de A 0 et B1.

Exemple

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

Output – 3

Instructions

Le sous-ensemble le plus long est { "0", "0", "1"}, qui contient 2 0 et 1 1.

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

Output – 3

Instructions

Le sous-ensemble le plus long est {"0", "101", "0", "1"}, 3 0 et 3 1.

Méthode 1

Dans cette section, nous allons apprendre une méthode simple utilisant la récursivité. Nous construirons tous les sous-ensembles possibles en utilisant les éléments du tableau et trouverons le sous-ensemble le plus long contenant A 0 et B 1 .

Algorithme

• Étape 1 - Définissez la fonction countZeros() pour compter le nombre total de zéros dans une chaîne binaire donnée.

• Étape 1.1 - Initialisez la variable "count" à zéro.

• Étape 1.2 - Utilisez une boucle for pour parcourir la chaîne.

• Étape 1.3 - Si le caractère au i-ième index est "0", alors augmentez la valeur de "cnt" de 1.

• Étape 1.2 - Renvoyez la valeur de la variable "cnt".

• Étape 2 - getMaxSubsetLen() renvoie une valeur entière et prend le vecteur arr, int A, int B et index comme arguments.

• Étape 3 - Définissez le cas de base au sein de la fonction. Renvoie 0 si l'index est égal à la taille du vecteur, ou si les valeurs de A et B sont toutes deux nulles.

• Étape 4 - Maintenant, comptez le nombre total de zéros dans la chaîne à l'index.

• Étape 5 - Soustrayez le nombre total de 1 de la longueur de la chaîne pour obtenir le nombre total de 1.

• Étape 6 - Initialisez la "première" variable à 0.

• Étape 7 - Contient la chaîne binaire actuelle si le nombre total de 0 et 1 est inférieur à A et B respectivement. Stocke 1 + la valeur de retour d'un appel de fonction récursif. Lors d'un appel récursif, 0 et 1 sont soustraits de A et B.

• Étape 8 - Excluez la chaîne actuelle et stockez la valeur résultante dans la "seconde" variable.

• Étape 9 - Renvoyez la valeur maximale du premier et du deuxième.

Exemple

#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;
}

Sortie

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Complexité temporelle - O(2N) puisque nous trouvons tous les sous-ensembles possibles en utilisant N éléments du tableau.

Complexité spatiale - O(1)

Méthode 2

Nous avons optimisé la méthode ci-dessus dans cette section. Nous utilisons des méthodes de programmation dynamique pour résoudre ce problème. Il stocke le résultat de l’état précédent pour réduire la complexité temporelle du problème.

Algorithme

• Étape 1 - Définissez la fonction countZeros() pour compter le nombre total de zéros dans une chaîne binaire spécifique, tout comme nous l'avons fait dans la méthode ci-dessus.

• Étape 2 - Créez un vecteur 3D de taille A x B x N pour stocker le résultat de l'état précédent. Dans la liste, nous stockerons la longueur du sous-ensemble à l'index "I" lorsque le total 0 est égal à A et 1 est égal à B. De plus, transmettez-le comme argument à la fonction getMaxSubsetLen().

• Étape 3 - Définissez le cas de base comme nous l'avons fait dans la méthode ci-dessus.

• Étape 4 - Si la valeur de dpTable[A][B][index] est supérieure à 0, cela signifie que l'état a été calculé et que sa valeur est renvoyée.

• Étape 5 - Comptez le nombre total de 0 et de 1 dans la chaîne actuelle.

• Étape 6 - Obtenez la valeur résultante, incluant et excluant la chaîne actuelle.

• Étape 7 - Utilisez la fonction max() pour obtenir la valeur maximale du premier et du deuxième, stockez-la dans dpTable[A][B][index] et retournez

Exemple

#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;
}

Sortie

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Complexité temporelle - O(A*B*N) puisque nous devons remplir la liste 3D pour obtenir le résultat.

Complexité spatiale - O(A*B*N) car nous utilisons des listes 3D pour la méthode de programmation dynamique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!