Compruebe si es posible llenar completamente cada contenedor con la misma bola

Dados dos arreglos , arr[ ] C de contenedores y arr[ ] B de bolas , la tarea es encontrar si es posible llenar completamente cada contenedor con las bolas dadas, si cada contenedor solo puede almacenar bolas del mismo tipo. En el arreglo C , C[i] almacena el número máximo de bolas que puede almacenar el i-ésimo contenedor. En el arreglo B, B[i] almacena el tipo de la i-ésima bola.

Ejemplos:

Entrada: C = [1, 2, 3], B = [1, 2, 2, 2, 3, 3, 4, 4, 4]
Salida: SÍ
Explicación: llene el primer recipiente con la bola 1, el segundo con 2 bolas con número 3 y tercer contenedor con bola que tiene el número 2

Entrada: C = [2], B = [1, 2, 3]
Salida: NO
Explicación: no hay combinación posible para llenar los contenedores

Enfoque: La idea es usar Backtracking para verificar si es posible llenar todos los contenedores o no. Se puede observar que solo se necesita la frecuencia de cada tipo de pelota, por lo que almacenamos la frecuencia de cada tipo de pelota en un mapa . Veamos los pasos involucrados en la implementación de nuestro enfoque:

• Almacena la frecuencia del mismo tipo de bolas en un mapa.
• Llame a la función getans para verificar si es posible llenar los contenedores.
• Intenta llenar el recipiente con bolas cuya frecuencia sea más que igual a la capacidad del recipiente . Si es posible, devuélvalo verdadero , de lo contrario, retroceda y verifique si hay otras bolas.
• Si no existe ninguna combinación, devuelve falso .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// A boolean function that returns true if it's possible to
// completely fill the container else return false
bool getans(int i, vector<int> v, vector<int> q)
{
    // Base Case
    if (i == q.size())
        return true;
 
    // Backtracking
    for (int j = 0; j < v.size(); j++) {
        if (v[j] >= q[i]) {
            v[j] -= q[i];
            if (getans(i + 1, v, q)) {
                return true;
            }
            v[j] += q[i];
        }
    }
    return false;
}
 
// Function to check the conditions
void Check(vector<int> c, vector<int> b)
{
 
    // Storing frequencies
    map<int, int> m;
    for (int i = 0; i < b.size(); i++) {
        m[b[i]]++;
    }
    vector<int> v;
    for (auto i : m) {
        v.push_back(i.second);
    }
 
    // Function Call for backtracking
    bool check = getans(0, v, c);
    if (check)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<int> c = { 1, 3, 3 };
    vector<int> b = { 2, 2, 2, 2, 4, 4, 4 };
 
    // Function Call
    Check(c, b);
    return 0;
}

# Python 3 program for above approach
 
# A boolean function that returns true if it's possible to
# completely fill the container else return false
def getans(i, v, q):
   
    # Base Case
    if (i == len(q)):
        return True
 
    # Backtracking
    for j in range(len(v)):
        if(v[j] >= q[i]):
            v[j] -= q[i]
            if (getans(i + 1, v, q)):
                return True
            v[j] += q[i]
    return False
 
# Function to check the conditions
def Check(c, b):
   
    # Storing frequencies
    m = {}
    for i in range(len(b)):
        if b[i] in m:
            m[b[i]] += 1
        else:
            m[b[i]] = 1
    v = []
    for key,value in m.items():
        v.append(value)
 
    # Function Call for backtracking
    check = getans(0, v, c)
    if (check):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    c = [1, 3, 3]
    b = [2, 2, 2, 2, 4, 4, 4]
 
    # Function Call
    Check(c, b)
     
    # This code is contributed by ipg2016107.

// C# program for above approach
using System;
using System.Collections.Generic;
class GFG
{
   
    // A boolean function that returns true if it's possible
    // to completely fill the container else return false
    static bool getans(int i, List<int> v, int[] q)
    {
        // Base Case
        if (i == q.Length)
            return true;
 
        // Backtracking
        for (int j = 0; j < v.Count; j++) {
            if (v[j] >= q[i]) {
                v[j] -= q[i];
                if (getans(i + 1, v, q)) {
                    return true;
                }
                v[j] += q[i];
            }
        }
        return false;
    }
 
    // Function to check the conditions
    static void Check(int[] c, int[] b)
    {
 
        // Storing frequencies
        Dictionary<int, int> m = new Dictionary<int, int>();
        for (int i = 0; i < b.Length; i++)
            m[b[i]] = 0;
        for (int i = 0; i < b.Length; i++) {
            m[b[i]]++;
        }
        List<int> v = new List<int>();
        foreach(KeyValuePair<int, int> i in m)
        {
            v.Add(i.Value);
        }
 
        // Function Call for backtracking
        bool check = getans(0, v, c);
        if (check)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
 
    // Driver Code
    public static void Main()
    {
       
        // Given Input
        int[] c = { 1, 3, 3 };
        int[] b = { 2, 2, 2, 2, 4, 4, 4 };
 
        // Function Call
        Check(c, b);
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for above approach
 
// A boolean function that returns true if it's possible to
// completely fill the container else return false
function getans(i, v, q) {
  // Base Case
  if (i == q.length) return true;
 
  // Backtracking
  for (let j = 0; j < v.length; j++) {
    if (v[j] >= q[i]) {
      v[j] -= q[i];
      if (getans(i + 1, v, q)) {
        return true;
      }
      v[j] += q[i];
    }
  }
  return false;
}
 
// Function to check the conditions
function Check(c, b) {
  // Storing frequencies
  let m = new Map();
  for (let i = 0; i < b.length; i++) {
    if (m.has(b[i])) {
      m.set(b[i], m.get(b[i]) + 1);
    } else {
      m.set(b[i], 1);
    }
  }
 
  let v = [];
  for (i of m) {
    v.push(i[1]);
  }
 
  // Function Call for backtracking
  let check = getans(0, v, c);
  if (check) document.write("YES");
  else document.write("NO");
}
 
// Driver Code
 
// Given Input
let c = [1, 3, 3];
let b = [2, 2, 2, 2, 4, 4, 4];
 
// Function Call
Check(c, b);
 
// This code is contributed by _saurabh_jaiswal.
</script>

YES

Complejidad de tiempo: O(m^n), donde n es el tamaño de arr[ ] C y m es el tamaño de arr[ ] B.
  
Espacio auxiliar: O(m)