Problème
Chaque personne doit effectuer exactement un trajet. Un groupe peut partager un trajet si la somme de leurs poids ne dépasse pas la capacité maximale. Les regroupements sont libres ; l’ordre d’entrée n’a pas d’importance. Minimisez le nombre de trajets.
Implémentez elevator_rides(weights, capacity).
Entrée
weights : Le poids de chaque personne.
capacity : Le poids total maximal autorisé par trajet.
Sortie
Retournez le nombre minimal de trajets.
Contraintes
1 ≤ personnes ≤ 20. 1 ≤ capacité ≤ 1 000 000 000. Chaque poids est compris entre 1 et capacité.
Exemples
Entrée :
weights = [3, 4, 5]
capacity = 7
Sortie attendue :
expected = 2Entrée :
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;
Sortie attendue :
long long expected = 2;Entrée :
long[] weights = new long[] {3, 4, 5};
long capacity = 7;
Sortie attendue :
long expected = 2;Explication
Envoyez 3 + 4 ensemble et 5 séparément. Le poids total 12 ne peut pas tenir en un seul trajet avec une capacité de 7.
Entrée :
weights = [2, 2, 2]
capacity = 6
Sortie attendue :
expected = 1Entrée :
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;
Sortie attendue :
long long expected = 1;Entrée :
long[] weights = new long[] {2, 2, 2};
long capacity = 6;
Sortie attendue :
long expected = 1;Explication
Les trois personnes tiennent ensemble car 2 + 2 + 2 = 6.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Comme le nombre de personnes est petit, considère des sous-ensembles plutôt que des trajets individuels.
Indice 2
Pour chaque sous-ensemble, garde à la fois le nombre de trajets utilisés et le remplissage du dernier trajet.
Indice 3
Quand deux états utilisent le même nombre de trajets, préfère celui avec la charge courante la plus faible.
Complexité attendue
temps O(2^n * n), espace supplémentaire O(2^n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.