Dada una array arr[] que consta de N strings binarias y dos números enteros A y B , la tarea es encontrar la longitud del subconjunto más largo que consta como máximo de A 0 s y B 1 s.
Ejemplos:
Entrada: arr[] = {“1”, “0”, “0001”, “10”, “111001”}, A = 5, B = 3
Salida: 4
Explicación:
Una forma posible es seleccionar el subconjunto {arr [0], array[1], array[2], array[3]}.
El número total de 0 y 1 en todas estas strings es 5 y 3 respectivamente.
Además, 4 es la longitud del subconjunto más largo posible.Entrada: arr[] = {“0”, “1”, “10”}, A = 1, B = 1
Salida: 2
Explicación:
Una forma posible es seleccionar el subconjunto {arr[0], arr[1] }.
El número total de 0 y 1 en todas estas strings es 1 y 1 respectivamente.
Además, 2 es la longitud del subconjunto más largo posible.
Enfoque ingenuo: el enfoque más simple para resolver el problema anterior es usar la recursividad . En cada llamada recursiva, la idea es incluir o excluir la string actual. Una vez consideradas todas las posibilidades, imprima la longitud máxima del subconjunto obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count 0's in a string int count0(string s) { // Stores count of 0s int count = 0; // Iterate over characters of string for (int i = 0; i < s.size(); i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive function to find the length of // longest subset from an array of strings // with at most A 0's and B 1's int solve(vector<string> vec, int A, int B, int idx) { // If idx is equal to N // or A + B is equal to 0 if (idx == vec.size() || A + B == 0) { return 0; } // Stores the count of 0's in arr[idx] int zero = count0(vec[idx]); // Stores the count of 1's in arr[idx] int one = vec[idx].size() - zero; // Stores the length of the // subset if arr[i] is included int inc = 0; // If zero is less than or equal to A // and one is less than or equal to B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1); } // Stores the length of the subset // if arr[i] is excluded int exc = solve(vec, A, B, idx + 1); // Returns max of inc and exc return max(inc, exc); } // Function to find the length of the // longest subset from an array of // strings with at most A 0's and B 1's int MaxSubsetlength(vector<string> arr, int A, int B) { // Return return solve(arr, A, B, 0); } // Driver Code int main() { vector<string> arr = { "1", "0", "10" }; int A = 1, B = 1; cout << MaxSubsetlength(arr, A, B); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to count 0's in a string static int count0(String s) { // Stores count of 0s int count = 0; // Iterate over characters of string for (int i = 0; i < s.length(); i++) { // If current character is '0' if (s.charAt(i) == '0') { count++; } } return count; } // Recursive function to find the length of // longest subset from an array of strings // with at most A 0's and B 1's static int solve(String[] vec, int A, int B, int idx) { // If idx is equal to N // or A + B is equal to 0 if (idx == vec.length || A + B == 0) { return 0; } // Stores the count of 0's in arr[idx] int zero = count0(vec[idx]); // Stores the count of 1's in arr[idx] int one = vec[idx].length() - zero; // Stores the length of the // subset if arr[i] is included int inc = 0; // If zero is less than or equal to A // and one is less than or equal to B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1); } // Stores the length of the subset // if arr[i] is excluded int exc = solve(vec, A, B, idx + 1); // Returns max of inc and exc return Math.max(inc, exc); } // Function to find the length of the // longest subset from an array of // strings with at most A 0's and B 1's static int MaxSubsetlength(String[] arr, int A, int B) { // Return return solve(arr, A, B, 0); } public static void main (String[] args) { String[] arr = { "1", "0", "10" }; int A = 1, B = 1; System.out.print(MaxSubsetlength(arr, A, B)); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to count 0's in a string def count0(s): # Stores count of 0s count = 0 # Iterate over characters of string for i in range(len(s)): # If current character is '0' if (s[i] == '0'): count += 1 return count # Recursive function to find the length of # longest subset from an array of strings # with at most A 0's and B 1's def solve(vec, A, B, idx): # If idx is equal to N # or A + B is equal to 0 if (idx == len(vec) or A + B == 0): return 0 # Stores the count of 0's in arr[idx] zero = count0(vec[idx]) # Stores the count of 1's in arr[idx] one = len(vec[idx]) - zero # Stores the length of the # subset if arr[i] is included inc = 0 # If zero is less than or equal to A # and one is less than or equal to B if (zero <= A and one <= B): inc = 1 + solve(vec, A - zero, B - one, idx + 1) # Stores the length of the subset # if arr[i] is excluded exc = solve(vec, A, B, idx + 1) # Returns max of inc and exc return max(inc, exc) # Function to find the length of the # longest subset from an array of # strings with at most A 0's and B 1's def MaxSubsetlength(arr, A, B): # Return return solve(arr, A, B, 0) # Driver Code if __name__ == '__main__': arr = [ "1", "0", "10" ] A = 1 B = 1 print(MaxSubsetlength(arr, A, B)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count 0's in a string static int count0(string s) { // Stores count of 0s int count = 0; // Iterate over characters of string for(int i = 0; i < s.Length; i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive function to find the length of // longest subset from an array of strings // with at most A 0's and B 1's static int solve(List<string> vec, int A, int B, int idx) { // If idx is equal to N // or A + B is equal to 0 if (idx == vec.Count || A + B == 0) { return 0; } // Stores the count of 0's in arr[idx] int zero = count0(vec[idx]); // Stores the count of 1's in arr[idx] int one = vec[idx].Length - zero; // Stores the length of the // subset if arr[i] is included int inc = 0; // If zero is less than or equal to A // and one is less than or equal to B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1); } // Stores the length of the subset // if arr[i] is excluded int exc = solve(vec, A, B, idx + 1); // Returns max of inc and exc return Math.Max(inc, exc); } // Function to find the length of the // longest subset from an array of // strings with at most A 0's and B 1's static int MaxSubsetlength(List<string> arr, int A, int B) { // Return return solve(arr, A, B, 0); } // Driver Code public static void Main() { List<string> arr = new List<string>{ "1", "0", "10" }; int A = 1, B = 1; Console.WriteLine(MaxSubsetlength(arr, A, B)); } } // This code is contributed by ukasp
Javascript
<script> // JavaScript program to implement // the above approach // Function to count 0's in a string function count0(s) { // Stores count of 0s let count = 0; // Iterate over characters of string for (let i = 0; i < s.length; i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive function to find the length of // longest subset from an array of strings // with at most A 0's and B 1's function solve(vec, A, B, idx) { // If idx is equal to N // or A + B is equal to 0 if (idx == vec.length || A + B == 0) { return 0; } // Stores the count of 0's in arr[idx] let zero = count0(vec[idx]); // Stores the count of 1's in arr[idx] let one = vec[idx].length - zero; // Stores the length of the // subset if arr[i] is included let inc = 0; // If zero is less than or equal to A // and one is less than or equal to B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1); } // Stores the length of the subset // if arr[i] is excluded let exc = solve(vec, A, B, idx + 1); // Returns max of inc and exc return Math.max(inc, exc); } // Function to find the length of the // longest subset from an array of // strings with at most A 0's and B 1's function MaxSubsetlength(arr, A, B) { // Return return solve(arr, A, B, 0); } // Driver code let arr = [ "1", "0", "10" ]; let A = 1, B = 1; document.write(MaxSubsetlength(arr, A, B)); </script>
2
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Memoization , en función de las siguientes observaciones:
- Se puede observar que existe un subproblema superpuesto y una propiedad de subestructura óptima .
Por lo tanto, la idea es utilizar la programación dinámica para optimizar el enfoque anterior.- La idea es utilizar la programación dinámica de estado 3D.
- Supongamos que Dp(i, A, B) representa la longitud máxima del subconjunto con como máximo A 0 y B 1.
- Luego, la transición de estados se puede definir seleccionando una string en el i -ésimo índice o no,
- Dp(i, A, B) = Max(1+Dp(i+1, A- Z, BO), Dp(i+1, A, B)),
donde Z es el conteo de O s y O es el cuenta de 0 s.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count number // of 0s present in the string int count0(string s) { // Stores the count of 0s int count = 0; // Iterate over characters of string for (int i = 0; i < s.size(); i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive Function to find the length of // longest subset from given array of strings // with at most A 0s and B 1s int solve(vector<string> vec, int A, int B, int idx, vector<vector<vector<int> > >& dp) { // If idx is equal to N or // A + B is equal to 0 if (idx == vec.size() || A + B == 0) { return 0; } // If the state is already calculated if (dp[A][B][idx] > 0) { return dp[A][B][idx]; } // Stores the count of 0's int zero = count0(vec[idx]); // Stores the count of 1's int one = vec[idx].size() - zero; // Stores the length of longest // by including arr[idx] int inc = 0; // If zero is less than A // and one is less than B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1, dp); } // Stores the length of longest subset // by excluding arr[idx] int exc = solve(vec, A, B, idx + 1, dp); // Assign dp[A][B][idx] = max(inc, exc); // Return return dp[A][B][idx]; } // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s int MaxSubsetlength(vector<string> arr, int A, int B) { // Stores all Dp-states vector<vector<vector<int> > > dp( A + 1, vector<vector<int> >(B + 1, vector<int>(arr.size() + 1, 0))); // Return return solve(arr, A, B, 0, dp); } // Driver Code int main() { vector<string> arr = { "1", "0", "10" }; int A = 1, B = 1; cout << MaxSubsetlength(arr, A, B); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { // Function to count number // of 0s present in the string static int count0(String s) { // Stores the count of 0s int count = 0; // Iterate over characters of string for (int i = 0; i < s.length(); i++) { // If current character is '0' if (s.charAt(i) == '0') { count++; } } return count; } // Recursive Function to find the length of // longest subset from given array of strings // with at most A 0s and B 1s static int solve(String []vec, int A, int B, int idx, int dp[][][]) { // If idx is equal to N or // A + B is equal to 0 if (idx == vec.length || A + B == 0) { return 0; } // If the state is already calculated if (dp[A][B][idx] > 0) { return dp[A][B][idx]; } // Stores the count of 0's int zero = count0(vec[idx]); // Stores the count of 1's int one = vec[idx].length() - zero; // Stores the length of longest // by including arr[idx] int inc = 0; // If zero is less than A // and one is less than B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1, dp); } // Stores the length of longest subset // by excluding arr[idx] int exc = solve(vec, A, B, idx + 1, dp); // Assign dp[A][B][idx] = Math.max(inc, exc); // Return return dp[A][B][idx]; } // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s static int MaxSubsetlength(String []arr, int A, int B) { // Stores all Dp-states int dp[][][] = new int[A+1][B+1][arr.length+1]; // Return return solve(arr, A, B, 0, dp); } // Driver Code public static void main (String[] args) { String arr[] = { "1", "0", "10" }; int A = 1, B = 1; System.out.println(MaxSubsetlength(arr, A, B)); } } // This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach # Function to count number # of 0s present in the string def count0(s): # Stores the count of 0s count = 0 # Iterate over characters of string for i in range(len(s)): # If current character is '0' if (s[i] == '0'): count+=1 return count # Recursive Function to find the length of # longest subset from given array of strings # with at most A 0s and B 1s def solve(vec, A, B, idx, dp): # If idx is equal to N or # A + B is equal to 0 if (idx == len(vec) or (A + B) == 0): return 0 # If the state is already calculated if (dp[A][B][idx] > 0): return dp[A][B][idx] # Stores the count of 0's zero = count0(vec[idx]) # Stores the count of 1's one = len(vec[idx]) - zero # Stores the length of longest # by including arr[idx] inc = 0 # If zero is less than A # and one is less than B if (zero <= A and one <= B): inc = 1 + solve(vec, A - zero, B - one, idx + 1, dp) # Stores the length of longest subset # by excluding arr[idx] exc = solve(vec, A, B, idx + 1, dp) # Assign dp[A][B][idx] = max(inc, exc) # Return return dp[A][B][idx] # Function to find the length of the # longest subset of an array of strings # with at most A 0s and B 1s def MaxSubsetlength(arr, A, B): # Stores all Dp-states dp = [[ [0 for col in range(len(arr) + 1)] for col in range(B + 1)] for row in range(A + 1)] # Return return solve(arr, A, B, 0, dp) arr = [ "1", "0", "10" ] A, B = 1, 1 print(MaxSubsetlength(arr, A, B)) # This code is contributed by suresh07.
C#
using System; public class GFG{ // Function to count number // of 0s present in the string static int count0(string s) { // Stores the count of 0s int count = 0; // Iterate over characters of string for (int i = 0; i < s.Length; i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive Function to find the length of // longest subset from given array of strings // with at most A 0s and B 1s static int solve(string []vec, int A, int B, int idx, int[,,] dp) { // If idx is equal to N or // A + B is equal to 0 if (idx == vec.Length || A + B == 0) { return 0; } // If the state is already calculated if (dp[A,B,idx] > 0) { return dp[A,B,idx]; } // Stores the count of 0's int zero = count0(vec[idx]); // Stores the count of 1's int one = vec[idx].Length - zero; // Stores the length of longest // by including arr[idx] int inc = 0; // If zero is less than A // and one is less than B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1, dp); } // Stores the length of longest subset // by excluding arr[idx] int exc = solve(vec, A, B, idx + 1, dp); // Assign dp[A,B,idx] = Math.Max(inc, exc); // Return return dp[A,B,idx]; } // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s static int MaxSubsetlength(string []arr, int A, int B) { // Stores all Dp-states int[,,] dp = new int[A+1,B+1,arr.Length+1]; // Return return solve(arr, A, B, 0, dp); } // Driver Code static public void Main () { string[] arr = { "1", "0", "10" }; int A = 1, B = 1; Console.WriteLine(MaxSubsetlength(arr, A, B)); } } // This code is contributed by rag2127
Javascript
<script> // Javascript program for the above approach // Function to count number // of 0s present in the string function count0(s) { // Stores the count of 0s let count = 0; // Iterate over characters of string for (let i = 0; i < s.length; i++) { // If current character is '0' if (s[i] == '0') { count++; } } return count; } // Recursive Function to find the length of // longest subset from given array of strings // with at most A 0s and B 1s function solve(vec, A, B, idx, dp) { // If idx is equal to N or // A + B is equal to 0 if (idx == vec.length || A + B == 0) { return 0; } // If the state is already calculated if (dp[A][B][idx] > 0) { return dp[A][B][idx]; } // Stores the count of 0's let zero = count0(vec[idx]); // Stores the count of 1's let one = vec[idx].length - zero; // Stores the length of longest // by including arr[idx] let inc = 0; // If zero is less than A // and one is less than B if (zero <= A && one <= B) { inc = 1 + solve(vec, A - zero, B - one, idx + 1, dp); } // Stores the length of longest subset // by excluding arr[idx] let exc = solve(vec, A, B, idx + 1, dp); // Assign dp[A][B][idx] = Math.max(inc, exc); // Return return dp[A][B][idx]; } // Function to find the length of the // longest subset of an array of strings // with at most A 0s and B 1s function MaxSubsetlength(arr, A, B) { // Stores all Dp-states let dp = new Array(A+1); for(let i = 0; i < A + 1; i++) { dp[i] = new Array(B+1); for(let j = 0; j < B+1;j++) { dp[i][j] = new Array(arr.length+1); for(let k = 0; k < arr.length + 1; k++) { dp[i][j][k] = 0; } } } // Return return solve(arr, A, B, 0, dp); } // Driver Code let arr = [ "1", "0", "10" ]; let A = 1, B = 1; document.write(MaxSubsetlength(arr, A, B)); // This code is contributed by avanitrachhadiya2155 </script>
2
Complejidad temporal: O(N*A*B)
Espacio auxiliar: O(N*A*B)
Publicación traducida automáticamente
Artículo escrito por sukritidawar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA