Número máximo de strings que se pueden formar con ceros y unos dados

Dada una lista de strings arr[] de ceros y unos solamente y dos enteros N y M , donde N es el número de 1 y M es el número de 0 . La tarea es encontrar el número máximo de strings de la lista dada de strings que se pueden construir con el número dado de 0 y 1.

Ejemplos: 

Entrada: arr[] = {“10”, “0001”, “11100”, “1”, “0”}, M = 5, N = 3 Salida: 4 Explicación: Las 4 strings que se pueden 
formar usando 
cinco 
0 y tres 1 son: “10”, “0001”, “1”, “0”

Entrada: arr[] = {“10”, “00”, “000” “0001”, “111001”, “1”, “0”}, M = 3, N = 1 Salida: 3 Explicación 
: Las 
3 
strings que se pueden formar con tres 0 y un 1 son: “00”, “1”, “0” 
 

Enfoque ingenuo: la idea es generar todas las combinaciones de la lista dada de strings y verificar el conteo de ceros y unos que satisfacen la condición dada. Pero la complejidad temporal de esta solución es exponencial. 

 Intuición:

Lo primero que veremos es que

• De la array de strings dada, tenemos que elegir algunos de sus índices, de modo que después de elegirlos contaremos nuestros unos y ceros.
• Entonces, este es un tipo de opción, supongamos que comenzamos a atravesar nuestro vector dado y nos paramos en cualquier i-ésimo índice, entonces para ese índice tenemos una opción.
• ¿Y qué elección es esa? La elección es que nos preguntaremos si incluir esta string en nuestra respuesta o no.
• Entonces, si decidimos elegir esta string en nuestra respuesta, agregaremos el recuento de unos y ceros de esta string en nuestra respuesta y seguiremos adelante, y si decidimos no incluir esta string en nuestra respuesta, entonces no haremos nada, simplemente avanzamos.
• Entonces, en general, podemos decir que tenemos una opción para cada índice de array si incluir nuestra respuesta o no incluirla.
• Y cada vez que escuchamos un término que aquí tenemos una opción como esta, entonces diremos que la recursión se usará aquí.
• ¿Por qué recursión? La recursividad se debe a que probará todas las posibilidades para cada string en nuestra respuesta.

// C++ program for the above Naive approach
#include <bits/stdc++.h>
using namespace std;
 // Count one and Zero function take string as parameter and count the number of ones and zeroes present in the string and return the counts.
    pair<int, int> countOneAndZero(string s)
    {
        int one = 0, zero = 0;
         
        for(int i = 0; i < s.length(); i++) // travel in the string
        {
            if(s[i] == '1')  // if == '1', then add to one
                one++;
            else            // otherwise add to zero
                zero++;
        }
         
        return {one, zero};
    }
int countString(int i, int one, int zero, int& maxZero, int& maxOne,
             vector<string>& arr)
    {
        if(i >= arr.size()) // if ith index crosses the length then return 0
            return 0;
         
        // if any of the count, crosses the criteria of having maximum one
        // or zero, then return 0
        if(one > maxOne || zero > maxZero)
            return 0;
         
        /* what we discused:-
        for every ith index i, we have two option, whether to include it
         in our answer or not, if include then add the count of
         ones and zeros from that string */
         
        // pair p contains, the number of ones and zeroes present in the string of ith index of vector arr.
        pair<int, int> p = countOneAndZero(arr[i]);
         
        /* we declare three variables -
        1) ans1, If adding the count of ones and zeroes at ith index in arr,
        does not crosses our limit, then to include this in our answer.
        2) ans2, If adding the count of ones and zeroes at ith index in arr,
        does not crosses our limit, then not to include this in our answer.
        3) ansWithout, If adding the count of ones and zeroes at ith index in arr, crosses our limit, then not to include this in our answer.
        */
         
        int ans1 = 0, ans2 = 0, ansWithout = 0;
         
        // adding count of current index, not to cross our limit then-
        if(one + p.first <= maxOne && zero + p.second <= maxZero)
        {
            // ans1, including it in our answer
            ans1 = 1 + countString(i + 1, one + p.first, zero + p.second,
                           maxZero, maxOne, arr);
             
            // not including in our answer.
            ans2 = countString(i + 1, one, zero, maxZero, maxOne, arr);
        }
        else // if crossing limit, obviously not to take
        {
            ansWithout = countString(i + 1, one, zero, maxZero, maxOne, arr);
        }
         
        // and at last return the maximum of them
        return max({ans1, ans2, ansWithout});
         
         
    }
                 
int main() {
 
    vector<string> arr = { "10", "0001", "1",
                           "111001", "0" };
  
    // N 0's and M 1's
    int N = 3, M = 5;
    
    int idx=0;
    int one=0;
    int zero=0;
    // Function call
    cout << countString(idx,one,zero,M, N, arr);
}
 
//This code is Contributed by Suchi

Complejidad de tiempo: O( 2 ^N ), donde N es el número de strings en la lista.

Enfoque Eficiente: 
Se da una solución eficiente usando Programación Dinámica . La idea es utilizar la recursión para generar todas las combinaciones posibles y almacenar los resultados de los subproblemas superpuestos durante la recursión . 

A continuación se muestran los pasos:  

• La idea es usar una array 3D dp ( dp[M][N][i] ) donde N y M son el número de 1 y 0 respectivamente e i es el índice de la string en la lista.
• Encuentre el número de 1 y 0 en la string actual y verifique si el conteo de ceros y unos es menor o igual al conteo dado N y M respectivamente.
• Si la condición anterior es verdadera, verifique si el valor del estado actual está almacenado en la tabla dp o no. En caso afirmativo, devuelva este valor.
• De lo contrario, muévase recursivamente para la siguiente iteración incluyendo y excluyendo la string actual como:

// By including the current string
x = 1 + recursive_function(M - zero, N - ones, arr, i + 1)

// By excluding the current string 
y = recursive_function(M, N, arr, i + 1)

// and update the dp table as:
dp[M][N][i] = max(x, y)

• El valor máximo de las dos llamadas recursivas anteriores dará el número máximo con N 1 y M 0 para el estado actual.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// 3D dp table to store the state value
int dp[100][100][100];
 
// Function that count the combination
// of 0's and 1's from the given list
// of string
int countString(int m, int n,
                vector<string>& arr, int i)
{
    // Base Case if count of 0's or 1's
    // becomes negative
    if (m < 0 || n < 0) {
        return INT_MIN;
    }
 
    // If index reaches out of bound
    if (i >= arr.size()) {
        return 0;
    }
 
    // Return the prestored result
    if (dp[m][n][i] != -1) {
        return dp[m][n][i];
    }
 
    // Initialize count of 0's and 1's
    // to 0 for the current state
    int zero = 0, one = 0;
 
    // Calculate the number of 1's and
    // 0's in current string
    for (char c : arr[i]) {
        if (c == '0') {
            zero++;
        }
        else {
            one++;
        }
    }
 
    // Include the current string and
    // recurr for the next iteration
    int x = 1 + countString(m - zero,
                            n - one,
                            arr, i + 1);
 
    // Exclude the current string and
    // recurr for the next iteration
    int y = countString(m, n, arr, i + 1);
 
    // Update the maximum of the above
    // two states to the current dp state
    return dp[m][n][i] = max(x, y);
}
 
// Driver Code
int main()
{
    vector<string> arr = { "10", "0001", "1",
                           "111001", "0" };
 
    // N 0's and M 1's
    int N = 3, M = 5;
 
    // Initialize dp array to -1
    memset(dp, -1, sizeof(dp));
 
    // Function call
    cout << countString(M, N, arr, 0);
}

// Java program for the above approach
class GFG{
  
// 3D dp table to store the state value
static int [][][]dp = new int[100][100][100];
  
// Function that count the combination
// of 0's and 1's from the given list
// of String
static int countString(int m, int n,
                String []arr, int i)
{
    // Base Case if count of 0's or 1's
    // becomes negative
    if (m < 0 || n < 0) {
        return Integer.MIN_VALUE;
    }
  
    // If index reaches out of bound
    if (i >= arr.length) {
        return 0;
    }
  
    // Return the prestored result
    if (dp[m][n][i] != -1) {
        return dp[m][n][i];
    }
  
    // Initialize count of 0's and 1's
    // to 0 for the current state
    int zero = 0, one = 0;
  
    // Calculate the number of 1's and
    // 0's in current String
    for (char c : arr[i].toCharArray()) {
        if (c == '0') {
            zero++;
        }
        else {
            one++;
        }
    }
  
    // Include the current String and
    // recurr for the next iteration
    int x = 1 + countString(m - zero,
                            n - one,
                            arr, i + 1);
  
    // Exclude the current String and
    // recurr for the next iteration
    int y = countString(m, n, arr, i + 1);
  
    // Update the maximum of the above
    // two states to the current dp state
    return dp[m][n][i] = Math.max(x, y);
}
  
// Driver Code
public static void main(String[] args)
{
    String []arr = { "10", "0001", "1",
                           "111001", "0" };
  
    // N 0's and M 1's
    int N = 3, M = 5;
  
    // Initialize dp array to -1
    for(int i = 0;i<100;i++){
        for(int j = 0;j<100;j++){
            for(int l=0;l<100;l++)
            dp[i][j][l]=-1;
        }
    }
  
    // Function call
    System.out.print(countString(M, N, arr, 0));
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program for the above approach
import sys
 
# 3D dp table to store the state value
dp = [[[-1 for i in range(100)]for j in range(100)] for k in range(100)]
 
# Function that count the combination
# of 0's and 1's from the given list
# of string
def countString(m, n, arr, i):
     
    # Base Case if count of 0's or 1's
    # becomes negative
    if (m < 0 or n < 0):
        return -sys.maxsize - 1
 
    # If index reaches out of bound
    if (i >= len(arr)):
        return 0
 
    # Return the prestored result
    if (dp[m][n][i] != -1):
        return dp[m][n][i]
 
    # Initialize count of 0's and 1's
    # to 0 for the current state
    zero = 0
    one = 0
 
    # Calculate the number of 1's and
    # 0's in current string
    for c in arr[i]:
        if (c == '0'):
            zero += 1
        else:
            one += 1
 
    # Include the current string and
    # recurr for the next iteration
    x = 1 + countString(m - zero, n - one, arr, i + 1)
 
    # Exclude the current string and
    # recurr for the next iteration
    y = countString(m, n, arr, i + 1)
     
    dp[m][n][i] = max(x, y)
 
    # Update the maximum of the above
    # two states to the current dp state
    return dp[m][n][i]
 
# Driver Code
if __name__ == '__main__':
    arr = ["10", "0001", "1","111001", "0"]
 
    # N 0's and M 1's
    N = 3
    M = 5
 
    # Function call
    print(countString(M, N, arr, 0))
     
# This code is contributed by Surendra_Gangwar

// C# program for the above approach
using System;
 
class GFG{
   
// 3D dp table to store the state value
static int [,,]dp = new int[100, 100, 100];
   
// Function that count the combination
// of 0's and 1's from the given list
// of String
static int countString(int m, int n,
                String []arr, int i)
{
    // Base Case if count of 0's or 1's
    // becomes negative
    if (m < 0 || n < 0) {
        return int.MinValue;
    }
   
    // If index reaches out of bound
    if (i >= arr.Length) {
        return 0;
    }
   
    // Return the prestored result
    if (dp[m, n, i] != -1) {
        return dp[m, n, i];
    }
   
    // Initialize count of 0's and 1's
    // to 0 for the current state
    int zero = 0, one = 0;
   
    // Calculate the number of 1's and
    // 0's in current String
    foreach (char c in arr[i].ToCharArray()) {
        if (c == '0') {
            zero++;
        }
        else {
            one++;
        }
    }
   
    // Include the current String and
    // recurr for the next iteration
    int x = 1 + countString(m - zero,
                            n - one,
                            arr, i + 1);
   
    // Exclude the current String and
    // recurr for the next iteration
    int y = countString(m, n, arr, i + 1);
   
    // Update the maximum of the above
    // two states to the current dp state
    return dp[m, n, i] = Math.Max(x, y);
}
   
// Driver Code
public static void Main(String[] args)
{
    String []arr = { "10", "0001", "1",
                           "111001", "0" };
   
    // N 0's and M 1's
    int N = 3, M = 5;
   
    // Initialize dp array to -1
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            for(int l = 0; l < 100; l++)
            dp[i, j, l] = -1;
        }
    }
   
    // Function call
    Console.Write(countString(M, N, arr, 0));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program for the above approach
  
// 3D dp table to store the state value
let dp = new Array();
 
// Initialize dp array to -1
for(let i = 0; i < 100; i++)
{
    dp[i] = new Array();
     for(let j = 0; j < 100; j++)
     {
          dp[i][j] = new Array();
        for(let l = 0; l < 100; l++)
        {
            dp[i][j][l] = -1;
        }
     }
} 
  
// Function that count the combination
// of 0's and 1's from the given list
// of String
function countString(m, n, arr, i)
{
     
    // Base Case if count of 0's or 1's
    // becomes negative
    if (m < 0 || n < 0)
    {
        return Number.MIN_VALUE;
    }
  
    // If index reaches out of bound
    if (i >= arr.length)
    {
        return 0;
    }
  
    // Return the prestored result
    if (dp[m][n][i] != -1)
    {
        return dp[m][n][i];
    }
  
    // Initialize count of 0's and 1's
    // to 0 for the current state
    let zero = 0, one = 0;
  
    // Calculate the number of 1's and
    // 0's in current String
    for(let c = 0; c < arr[i].length; c++)
    {
        if (arr[i] == '0')
        {
            zero++;
        }
        else
        {
            one++;
        }
    }
  
    // Include the current String and
    // recurr for the next iteration
    let x = 1 + countString(m - zero,
                            n - one,
                       arr, i + 1);
  
    // Exclude the current String and
    // recurr for the next iteration
    let y = countString(m, n, arr, i + 1);
  
    // Update the maximum of the above
    // two states to the current dp state
    return dp[m][n][i] = Math.max(x, y);
}
  
// Driver Code
let arr = [ "10", "0001", "1", "111001", "0" ];
 
// N 0's and M 1's
let N = 3, M = 5;
 
// Function call
document.write(countString(M, N, arr, 0));
 
// This code is contributed by Dharanendra L V.
 
</script>

4

Complejidad de tiempo: O(N*M*len), donde N y M son los números de 1 y 0 respectivamente y len es la longitud de la lista.
Espacio auxiliar: O(N*M*len)