Bonjour !

J'essaye de trouver un bon algorithme pour résoudre ce problème, mais je n'y arrive pas, quelqu'un pourrait-il s'y intéresser ?


Voici en quoi consiste le problème :

On souhaite optimiser l’ordre de construction de mines.

Une mine est un bâtiment qui a un coût, mais qui rapporte une certaine somme d’argent tous les jours. On a à notre disposition plusieurs mines qu’il est possible de construire, à condition bien entendu d’avoir l’argent nécessaire pour les payer. Le but du jeu est de construire toutes ces mines en un minimum de temps. En effet, on se rend compte que l’ordre de construction des mines a son importance, puisque les mines rapportent de l’argent une fois construites, et qu’elles minimisent donc le temps d’attente avant la construction des mines suivantes. Le but de l’algorithme est de trouver l’ordre de construction idéal, qui nécessite un temps total minimal.

Je n’ai pas réussi à trouver d’algorithme intelligent, autre que le test de toutes les combinaisons possibles.

On a à notre disposition n mines.
Chaque mine M_i a un coût c_i et une production p_i.
Au départ, on n’a pas d’argent, mais on gagne p argent par jour.
On considère ici que les mines n’ont pas de temps de construction, c’est-à-dire qu’une fois payées, elles sont fonctionnelles instantanément.

Soit T_i le temps d’attente avant la construction de la mine M_i.

On a T_i = c_i / (p + somme pour j allant de 1 à i-1 de p_j)

Le but est donc de minimiser la somme des T_i.


Voilà ! Si quelqu'un a une idée, merci d'avance !