Combinatoria con PHP

[manueltg]

Hola a todos, estoy realizando un pequeño ejercicio en PHP, y me he quedado realmente bloqueado, os cuento el problema:

Por ejemplo, tenemos una serie de habitaciones en un hotel, que tienen una capacidad:

Código PHP:

   
//contiene las capacidades de las habitaciones 
$rooms = [1,2,4,6]; 
 
//contiene el numero de veces que se puede repetir cada habitacion como maximo 
$disponibilidad = [3,4,2];  
   

Lo que quiero es encontrar una solución que me proporcione una combinación de esos elementos que satisfaga una serie de condiciones, como por ejemplo, que el numero de personas que se vayan a hospedar sea igual que el total de la combinación, y que el tamaño de la combinación sea establecido previamente.

Una posible solución sería:

Para 10 personas, una buena solución sería:

[6,4]

Una habitación de 6 personas y una de 4 personas.

Gracias de antemano, un saludo.

[xerifandtomas]

Yo iria comprobando con un bucle si el numero total cabe en cada habitación.
A ver me explico
Para diez personas:
Personas > 0 , si, continuo
Si 10 es >= a la habitacion mas grande (6);
Si se cumple restaria el tamaño de la habitación al nº personas (10-6=4);
Y vuelvo a comprobar;
Personas > 0, si, continuo
Si 4 >=6; no se cumple, paso con la siguiente habitación;
Si 4>=4; se cumple, resto 4-4=0; y vuelvo a comenzar el bucle;
Personas > 0, no finalizo

Y asi sucesivamente para cualquier numero.

Espero me hayas entendido el concepto.

Para hacerlo puedes utilizar while

[Karmac]

mmm Empecé a hacer el ejercicio pero planteé mal tus variables me parece. Lo siento, no las entendía. Te dejo el código que me ha quedado a ver si te sirve de ayuda. Cualquier duda dime.

Código PHP:

<?php
 
// Cantidad de personas, obtenido de un formulario por ejemplo.
$guests = 10;
 
$rooms = array(
    // Número de la habitación - Capacidad
    'hab1'  =>  3,
    'hab2'  =>  3,
    'hab3'  =>  4,
    'hab4'  =>  2
);
 
// Ordenamos las habitaciones por tamaño.
asort($rooms);
$rooms = array_reverse($rooms);
 
// Bucle.
// Comprobamos las habitaciones de mayor a menor capacidad.
// Si el tamaño es menor al número de huéspedes se asignan a
// esa habitación hasta llenarla y se procede con la siguiente en orden.
$selectedRooms = array();
foreach ( $rooms as $key => $value )
{
    if ( $guests >= $value )
    {
        $guests -= $value;
        $selectedRooms[] = $key;
    }
}
 
// Comprobamos si queda algún huésped sin habitación.
if ( $guests != 0 )
{
    echo 'Lo sentimos, pero no se pueden acoger a todos los huéspedes en nuestro hotel.';
}
else
{
    echo 'Las habitaciones que se les han asignado son las siguientes: ' . implode(', ', $selectedRooms);
}
?>
 

Saludos.

EDITO: por lo que se ve @xerifandtomas se me ha adelantado respondiendo mientras preparada la movida ;P Creo que en su post se refiere a lo mismo que he hecho en mi código.

[manueltg]

Hola de nuevo, ante todo muchas gracias a los dos por las respuestas, creo que no me he terminado de explicar bien, se me ha pasado un detalle importante, no sólo es distribuir a la gente como yo quiera sino que, además tendre que distribuirla en X habitaciones de ahí la complejidad del problema... cuando me refiero a que tengo una serie de condiciones, me refiero a:

El usuario me dice, cuantas personas se van a hospedar en el hotel, y además me da el número de habitaciones que quiere yo tengo que ser capaz de devolverle un resultado acorde con su consulta, es decir, si en mi hotel tengo 5 tipos de habitaciones donde las capacidades son:

Código PHP:

  $habitaciones = [2,3,4,5,6]  
   

Además de esas habitaciones sólo tengo:

Código PHP:

  $disponibilidad = [2,1,3,4,2]  
   

El cliente me solicita 3 habitaciones, para 10 personas, una buena solución para este caso sería:

-Dos habitaciones de 5 personas

Un saludo.

[dashtrash]

- Necesitas todas las disponibilidades distintas.Es decir, si tienes 3 habitaciones de [1,2,1] plazas, las disponibilidades distintas son [1,2].
- Se ordenan de mayor a menor disponibilidad
- Se recorre el array de disponibilidades creando árboles.En cada iteración,. la raiz del arbol es k , y se busca una combinación válida con las disponibilidades a partir de k.
- Si la suma de disponibilidades a una profundidad del árbol = número de habitaciones , es menor que el número de plazas requeridas, se elimina esa combinacion.
Esto incluye profundidad 1.Es decir, si se piden 2 plazas en 1 habitacion, y existen habitaciones de 1 plaza, significa que a profundidad 1 del arbol, la suma de disponibilidades (1) es menor que el numero requerido (2 plazas), por lo que no se continua con el arbol (no se comprueba el arbol con raiz 1).


Esto es una forma de hacerlo que evita hacer combinatoria, aunque sigue dando resultados absurdos que habría que filtrar, pero eso no especificas como.Si hay habitaciones de 5 plazas, y alguien pide 2 habitaciones para 2 personas, no tiene logica que se le ofrezcan 2 habitaciones de 5 plazas.