Número mínimo de contenedores requeridos para colocar N artículos (Usando el algoritmo Best Fit)

Dada una array peso[] que consta de pesos de N elementos y un número entero positivo C que representa la capacidad de cada contenedor, la tarea es encontrar el número mínimo de contenedores necesarios para que todos los elementos se asignen a uno de los contenedores.

Ejemplos:

Entrada: peso[] = {4, 8, 1, 4, 2, 1}, C = 10
Salida: 2
Explicación: El número mínimo de contenedores necesarios para acomodar todos los artículos es 2.
El primer contenedor contiene los artículos con pesos { 4, 4, 2}.
El segundo contenedor contiene los artículos con pesos {8, 1, 1}.

Entrada: peso[] = {9, 8, 2, 2, 5, 4}, C = 10
Salida: 4

Enfoque: El problema dado se puede resolver utilizando el algoritmo de mejor ajuste . La idea es colocar el siguiente artículo en la papelera, donde queda el menor espacio vacío. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar como 0 que almacene la cantidad mínima de contenedores requeridos.
• Ordene el peso de array dado [] en orden decreciente .
• Inicialice un conjunto múltiple , diga M para almacenar los espacios vacíos que quedan en los contenedores ocupados actualmente.
• Recorra el peso de la array [] y para cada elemento realice los siguientes pasos:
  • Si existe el espacio vacío más pequeño que es al menos arr[i] está presente en M , entonces borre ese espacio de M e inserte el espacio libre restante en M .
  • De lo contrario, incremente el conteo en 1 e inserte el espacio vacío del nuevo contenedor en M .
• Después de completar los pasos anteriores, imprima el valor de conteo como el número mínimo de contenedores requeridos.

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

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the minimum number
// of bins required to fill all items
void bestFit(int arr[], int n, int W)
{
    // Stores the required number
    // of bins
    int count = 0;
  
    // Sort the array in decreasing order
    sort(arr, arr + n, greater<int>());
  
    // Stores the empty spaces in
    // existing bins
    multiset<int> M;
  
    // Traverse the given array
    for (int i = 0; i < n; i++) {
  
        // Check if exact space is
        // present in the set M
        auto x = M.find(arr[i]);
  
        // Store the position of the
        // upperbound of arr[i] in M
        auto y = M.upper_bound(arr[i]);
  
        // If arr[i] is present, then
        // use this space and erase it
        // from the map M
        if (x != M.end()) {
            M.erase(x);
        }
  
        // If upper bound of arr[i] is
        // present, use this space and
        // insert the left space
        else if (y != M.end()) {
            M.insert(*y - arr[i]);
            M.erase(y);
        }
  
        // Otherwise, increment the count
        // of bins and insert the
        // empty space in M
        else {
            count++;
            M.insert(W - arr[i]);
        }
    }
  
    // Print the result
    cout << count;
}
  
// Driver Code
int main()
{
    int items[] = { 4, 8, 1, 4, 2, 1 };
    int W = 10;
    int N = sizeof(items) / sizeof(items[0]);
  
    // Function Call
    bestFit(items, N, W);
  
    return 0;
}

2

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)