Il y a un problème sur lequel je travaille pour un cours de programmation et j'ai du mal à développer un algorithme adapté au problème. Le voici :
Vous partez pour un long voyage. Vous commencez la route au point kilométrique 0. Le long de la route, il y a n hôtels, aux bornes kilométriques a1 < a2 < ... < an, où chaque ai est mesuré à partir du point de départ. Le site seuls endroits où vous êtes autorisé à vous arrêter sont ces hôtels, mais vous pouvez choisir dans lesquels vous vous vous arrêtez. Vous devez vous arrêter à l'hôtel final (à la distance an), qui est votre destination. Dans l'idéal, vous aimeriez parcourir 200 miles par jour, mais cela peut ne pas être possible (en fonction de l'espacement des hôtels). Si vous parcourez x miles pendant une journée, la pénalité pour cette journée est de (200 - x)^2. Vous voulez planifier votre voyage de manière à minimiser la pénalité totale, c'est-à-dire la somme, sur tous les jours de voyage, des pénalités quotidiennes. pénalités quotidiennes. Donnez un algorithme efficace qui détermine la séquence optimale d'hôtels où s'arrêter.
Donc, mon intuition me dit de commencer par l'arrière, en vérifiant les valeurs de pénalité, puis de les faire correspondre d'une manière ou d'une autre en retournant vers l'avant (ce qui donne un temps d'exécution O(n^2), ce qui est suffisamment optimal pour la situation).
Quelqu'un voit-il un moyen de concrétiser cette idée ou a-t-il des idées sur des implémentations possibles ?
