Problema
Cada persona debe viajar exactamente una vez. Cualquier grupo puede compartir un viaje si la suma de sus pesos no supera la capacidad. Las personas pueden reagruparse libremente; el orden de entrada no importa. Minimiza el número de viajes.
Implementa elevator_rides(weights, capacity).
Entrada
weights: El peso de cada persona.
capacity: El peso máximo combinado en un viaje.
Salida
Devuelve el número mínimo de viajes.
Restricciones
1 ≤ personas ≤ 20. 1 ≤ capacidad ≤ 1,000,000,000. Cada peso está entre 1 y capacidad.
Ejemplos
Entrada:
weights = [3, 4, 5]
capacity = 7
Salida esperada:
expected = 2Entrada:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
Salida esperada:
long long expected = 2;Entrada:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
Salida esperada:
long expected = 2;Explicación
Envía a 3 + 4 juntos y a 5 por separado. El peso total 12 no cabe en un solo viaje de capacidad 7.
Entrada:
weights = [2, 2, 2]
capacity = 6
Salida esperada:
expected = 1Entrada:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
Salida esperada:
long long expected = 1;Entrada:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
Salida esperada:
long expected = 1;Explicación
Las tres personas caben juntas porque 2 + 2 + 2 = 6.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Como el número de personas es pequeño, considera subconjuntos en lugar de viajes individuales.
Pista 2
Lleva para cada subconjunto tanto cuántos viajes se usan como lo lleno que está el último viaje.
Pista 3
Cuando dos estados usan el mismo número de viajes, prefiere el que tenga menor carga actual.
Complejidad esperada
tiempo O(2^n * n), espacio extra O(2^n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.