Longitud del subconjunto más largo que consta de A 0 y B 1 de una array de strings | conjunto 2

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:
  • 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *