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>
Producción:
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:
Árbol de recursión
- 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>
Producción:
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