Discussion :

[alino0123]

Entrée :
Votre programme aura en entrée les données suivantes. Dans la première ligne on aura
une valeur entière exprimant le nombre de cas à traiter. Pour chaque cas on aura ensuite
une séquence de lignes suivantes:
- La première ligne contient un entier n qui exprime le nombre de différentes
catégories de véhicules disponibles pour ce cas. Vous pouvez présumer que n < 10.
- Chacune des n lignes suivantes (c-à-d chaque ligne i+1 pour i=1,2, … , n) contiendra
deux nombres spécifiant les paramètres suivants :
1. La capacité (nombre de passagers) d’un véhicule de type i
2. Le coût de location d’un véhicule de type i
- La dernière ligne de chaque cas contiendra le nombre total p de personnes qu’il
faut transporter.
Sortie :
Votre programme, pour chaque cas traité, doit afficher :
1. Le coût total de la location optimale.
2. Le nombre de véhicules loués pour chacune des catégories disponibles.
3. Le nombre totale de places inutilisées dans la sélection de véhicules que vous
avez proposée (c.-à-d. combien de passagers il serait possible d’ajouter à p sans
augmenter le coût de location).
Dans l’évaluation de votre programme, veuillez estimer la complexité de votre
algorithme en fonction de deux paramètres d’entrée: n et p (et possiblement d’autres -
selon votre jugement).
Exemple de l’entrée :
3
4
4 60
15 210
40 550
400 4800
1249
4
4 60
15 210
40 550
400 4800
1250
3
4 60
15 222
42 615
43
Exemple de sortie :
Cas 1 : Le coût total pour transporter 1249 personnes est de 15090 $. Il faut louer 3
véhicule(s) de catégorie 4, 3 véhicule(s) de catégorie 2 et 1 véhicule(s) de catégorie 1. Il
n’y a pas de places libres disponibles.
Cas 2 : Le coût total pour transporter 1250 personnes est de 15130 $. Il faut louer 3
véhicule(s) de catégorie 4, 1 véhicule(s) de catégorie 3 et 3 véhicule(s) de catégorie 1. Il y
aura 2 place(s) libre(s) disponible(s).
Cas 3 : Le coût total pour transporter 43 personnes est de 660 $. Il faut louer 11
véhicule(s) de catégorie 1. Il aura 1 place(s) libre(s) disponible(s).

[Christophe]

Bonjour,

Nous ne ferons pas l'exercice à ta place.

Nous t’aiderons si tu as des difficultés, mais commence déjà quelque chose.