Bonjour,

j'ai le problème suivant à résoudre;
Afin de commercialiser ses différents produits, une entreprise a besoin de n permis. A cause de certaines lois, elle ne peut obtenir plus d'un permis par mois. De plus, le coût des permis augmente
chaque mois. En effet, bien que le coût de chacun des permis soit de $100.00 actuellement, le coût du permis j (1 <= j <= n) augmente d'un facteur rj > 1 chaque mois (les rj sont des paramètres).
Autrement dit, acheter le permis 4 durant le premier mois coûte 100r4 alors que son acquisition durant le sixième mois, par exemple, coûterait 100(r4)^6 . Enfin, on suppose que ri ?=(différent) rj pour i ?=(différent) j.
La question est donc de savoir, pour un ensemble de rj donné (1 <= j <= n), dans quel ordre acheter les n permis afin de minimiser le coût total d'acquisition.
1. Elaborez un algorithme polynomial, utilisant l'approche vorace, permettant de résoudre ce problème. Analysez votre algorithme en pire cas.
2. Prouvez que votre algorithme retourne bien la solution optimale.
3. Illustrez votre algorithme sur l'instance suivante : n = 3, r1 = 3, r2 = 4, r3 = 2.
J'ai pu écrire seulement l'algorithme suivant, mais ne sait plus quoi écrire d'autre:

Algorithme minCout()

TantQue j<n (tant que tous les permis ne sont pas achetés)
j=prochain permis acheté
Si le permis du mois courant est disponible alors
acheter
Fsi
FTantQue


Pouvez vous m'aiguiller s'il vous plaît? Merci.