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: consulte la publicación anterior de este artículo para conocer el enfoque más simple para resolver el problema.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque de programación dinámica : consulte la publicación anterior de este artículo para conocer el enfoque de programación dinámica .
Complejidad de Tiempo: O(N*A*B)
Espacio Auxiliar: O(N * A * B)
Enfoque de programación dinámica optimizada para el espacio: la complejidad del espacio en el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Inicialice una array 2D, dp[A][B] , donde dp[i][j] representa la longitud del subconjunto más largo que consta como máximo de i número de 0 s y j número de 1 s.
- Para optimizar el espacio auxiliar de la mesa 3D a la mesa 2D , la idea es atravesar los bucles internos en orden inverso.
- Esto asegura que cada vez que se cambie un valor en dp[][] , ya no será necesario en la iteración actual.
- Por lo tanto, la relación de recurrencia se ve así:
dp[i][j] = max (dp[i][j], dp[i – zeros][j – ones] + 1)
donde ceros es el conteo de 0s y ones es el conteo de 1s en la iteración actual .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , diga dp[A][B] e inicialice todas sus entradas como 0 .
- Recorra la array dada arr[] y para cada string binaria realice los siguientes pasos:
- Almacene el conteo de 0 y 1 en la string actual en las variables ceros y unos respectivamente.
- Iterar en el rango [A, ceros] usando la variable i y simultáneamente iterar en el rango [B, unos] usando la variable j y actualizar el valor de dp[i][j] al máximo de dp[i][j] y (dp[i – ceros][j – unos] + 1) .
- Después de completar los pasos anteriores, imprima el valor de dp[A][B] como resultado.
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 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)
{
// Initialize a 2D array with its
// entries as 0
int dp[A + 1][B + 1];
memset(dp, 0, sizeof(dp));
// Traverse the given array
for (auto& str : arr) {
// Store the count of 0s and 1s
// in the current string
int zeros = count(str.begin(),
str.end(), '0');
int ones = count(str.begin(),
str.end(), '1');
// Iterate in the range [A, zeros]
for (int i = A; i >= zeros; i--)
// Iterate in the range [B, ones]
for (int j = B; j >= ones; j--)
// Update the value of dp[i][j]
dp[i][j] = max(
dp[i][j],
dp[i - zeros][j - ones] + 1);
}
// Print the result
return dp[A][B];
}
// Driver Code
int main()
{
vector<string> arr
= { "1", "0", "0001",
"10", "111001" };
int A = 5, B = 3;
cout << MaxSubsetlength(arr, A, B);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// 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)
{
// Initialize a 2D array with its
// entries as 0
int dp[][] = new int[A + 1][B + 1];
// Traverse the given array
for(String str : arr)
{
// Store the count of 0s and 1s
// in the current string
int zeros = 0, ones = 0;
for(char ch : str.toCharArray())
{
if (ch == '0')
zeros++;
else
ones++;
}
// Iterate in the range [A, zeros]
for(int i = A; i >= zeros; i--)
// Iterate in the range [B, ones]
for(int j = B; j >= ones; j--)
// Update the value of dp[i][j]
dp[i][j] = Math.max(
dp[i][j],
dp[i - zeros][j - ones] + 1);
}
// Print the result
return dp[A][B];
}
// Driver Code
public static void main(String[] args)
{
String arr[] = { "1", "0", "0001",
"10", "111001" };
int A = 5, B = 3;
System.out.println(MaxSubsetlength(arr, A, B));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# 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):
# Initialize a 2D array with its
# entries as 0
dp = [[0 for i in range(B + 1)]
for i in range(A + 1)]
# Traverse the given array
for str in arr:
# Store the count of 0s and 1s
# in the current string
zeros = str.count('0')
ones = str.count('1')
# Iterate in the range [A, zeros]
for i in range(A, zeros - 1, -1):
# Iterate in the range [B, ones]
for j in range(B, ones - 1, -1):
# Update the value of dp[i][j]
dp[i][j] = max(dp[i][j],
dp[i - zeros][j - ones] + 1)
# Print the result
return dp[A][B]
# Driver Code
if __name__ == '__main__':
arr = [ "1", "0", "0001", "10", "111001" ]
A, B = 5, 3
print (MaxSubsetlength(arr, A, B))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG {
// 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)
{
// Initialize a 2D array with its
// entries as 0
int[, ] dp = new int[A + 1, B + 1];
// Traverse the given array
foreach(string str in arr)
{
// Store the count of 0s and 1s
// in the current string
int zeros = 0, ones = 0;
foreach(char ch in str.ToCharArray())
{
if (ch == '0')
zeros++;
else
ones++;
}
// Iterate in the range [A, zeros]
for (int i = A; i >= zeros; i--)
// Iterate in the range [B, ones]
for (int j = B; j >= ones; j--)
// Update the value of dp[i][j]
dp[i, j] = Math.Max(
dp[i, j],
dp[i - zeros, j - ones] + 1);
}
// Print the result
return dp[A, B];
}
// Driver Code
public static void Main(string[] args)
{
string[] arr = { "1", "0", "0001", "10", "111001" };
int A = 5, B = 3;
Console.WriteLine(MaxSubsetlength(arr, A, B));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// 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)
{
// Initialize a 2D array with its
// entries as 0
var dp = Array.from(Array(A + 1),
()=>Array(B + 1).fill(0));
// Traverse the given array
arr.forEach(str => {
// Store the count of 0s and 1s
// in the current string
var zeros = [...str].filter(x => x == '0').length;
var ones = [...str].filter(x => x == '1').length;
// Iterate in the range [A, zeros]
for(var i = A; i >= zeros; i--)
// Iterate in the range [B, ones]
for(var j = B; j >= ones; j--)
// Update the value of dp[i][j]
dp[i][j] = Math.max(dp[i][j],
dp[i - zeros][j - ones] + 1);
});
// Print the result
return dp[A][B];
}
// Driver Code
var arr = [ "1", "0", "0001",
"10", "111001" ];
var A = 5, B = 3;
document.write(MaxSubsetlength(arr, A, B));
// This code is contributed by noob2000
</script>
4
Complejidad de Tiempo: O(N * A * B)
Espacio Auxiliar: O(A * B)
Publicación traducida automáticamente
Artículo escrito por yadavgaurav251 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA