Programa Php Para Problema De Distribución De Chocolate

Dada una array de n enteros donde cada valor representa la cantidad de chocolates en un paquete. Cada paquete puede tener un número variable de bombones. Hay m estudiantes, la tarea es distribuir paquetes de chocolate de tal manera que: 

1. Cada estudiante recibe un paquete.
2. La diferencia entre la cantidad de chocolates en el paquete con el máximo de chocolates y el paquete con el mínimo de chocolates que se les da a los estudiantes es mínima.

Ejemplos:

Entrada: arr[] = {7, 3, 2, 4, 9, 12, 56} , m = 3 
Salida: La diferencia mínima es 2 
Explicación:
Tenemos siete paquetes de chocolates y 
necesitamos elegir tres paquetes para 3 estudiantes 
Si elegimos 2, 3 y 4, obtenemos la diferencia mínima  entre los tamaños
de paquete máximo y mínimo  .

Entrada: arr[] = {3, 4, 1, 9, 56, 7, 9, 12}, m = 5 
Salida: La diferencia mínima es 6 
Explicación:
El conjunto va como 3,4,7,9,9 y el la salida 
es 9-3 = 6

Entrada: arr[] = {12, 4, 7, 9, 2, 23, 25, 41, 
30, 40, 28, 42, 30, 44, 48, 
43, 50}, m = 7 
Salida: La diferencia mínima es 10 
Explicación:
Necesitamos recoger 7 paquetes. Elegimos 40, 41, 
42, 44, 48, 43 y 50 para minimizar la diferencia 
entre el máximo y el mínimo. 

Fuente: Experiencia de entrevista Flipkart

Una solución simple es generar todos los subconjuntos de tamaño m de arr[0..n-1]. Para cada subconjunto, encuentre la diferencia entre los elementos máximo y mínimo en él. Finalmente, devuelva la diferencia mínima.
Una solución eficiente se basa en la observación de que para minimizar la diferencia, debemos elegir elementos consecutivos de un paquete ordenado. Primero ordenamos el arreglo arr[0..n-1], luego encontramos el subarreglo de tamaño m con la diferencia mínima entre el último y el primer elemento.

La imagen de abajo es una ejecución en seco del enfoque anterior:

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

<?php
// PHP program to solve chocolate 
// distribution problem
  
// arr[0..n-1] represents sizes of 
// packets m is number of students.
// Returns minimum difference between 
// maximum and minimum values of 
// distribution.
function findMinDiff($arr, $n, $m)
{
    // If there are no chocolates or 
    // number of students is 0
    if ($m == 0 || $n == 0)
        return 0;
  
    // Sort the given packets
    sort($arr);
  
    // Number of students cannot be 
    // more than number of packets
    if ($n < $m)
    return -1;
  
    // Largest number 
    // of chocolates
    $min_diff = PHP_INT_MAX;
  
    // Find the subarray of size m such 
    // that difference between last (
    // maximum in case of sorted) and 
    // first (minimum in case of sorted) 
    // elements of subarray is minimum.
      
    for ($i = 0; 
         $i + $m - 1 < $n; $i++)
    {
        $diff = $arr[$i + $m - 1] -
                $arr[$i];
        if ($diff < $min_diff)
            $min_diff = $diff;
    }
    return $min_diff;
}
  
// Driver Code
$arr = array(12, 4, 7, 9, 2, 23, 
             25, 41, 30, 40, 28, 
             42, 30, 44, 48, 43, 50);
          
// Number of students     
$m = 7; 
$n = sizeof($arr);
echo "Minimum difference is ",
      findMinDiff($arr, $n, $m);
// This code is contributed by ajit
?>

Producción:

Minimum difference is 10

Complejidad de tiempo: O (n Log n) ya que aplicamos la clasificación antes de la búsqueda de subarreglo.

¡ Consulte el artículo completo sobre el problema de distribución de chocolate para obtener más detalles!