Tous les défis
Difficile 1 résolu 100.0 % de réussite

Nombre minimum de trajets d’ascenseur

Regroupez les personnes en un nombre minimal de trajets d’ascenseur, chaque trajet étant limité par le poids maximal autorisé.

Ce que vous allez apprendre

  • Représenter des groupes de personnes par des masques de bits
  • Stocker par sous-ensemble les meilleurs trajets et le poids du dernier
  • Gérer astucieusement des espaces de recherche exponentiels

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

Exemple 1
Entrée :
weights = [3, 4, 5]
capacity = 7

Sortie attendue :
expected = 2
Entré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.

Exemple 2
Entrée :
weights = [2, 2, 2]
capacity = 6

Sortie attendue :
expected = 1
Entré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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 831 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.