Heyo,

J'ai le problème suivant en informatique :
Un voyageur va en Italie avec N pièces d'or et un itinéraire fixé de K villes A, B, C, D etc
À chaque ville un nombre de points de bonheur est associé
Le voyageur commence à la ville A puis à la B puis la C etc. jusqu'à ce qu'il n'ai plus de pièces d'or.
Il peut rester 1 jour ou 2 jours dans chaque ville à chaque ville, et 1 jour coûte 1 pièce d'or
Pour un jour passé dans une ville il gagne le nombre de points de bonheur qui lui est associé, et il arrête son voyage quand il n'a plus de pièces d'or.

Le but de programme que je dois créer est de renvoyer la liste avec l'itinéraire qui rapporte le plus de points de bonheur au voyageur.

J'ai essayé pas mal de choses (à chaque fois avec une boucle for et en comparant différentes ville/trajets) mais à chaque fois ça prend pas tous les trajets en compte et y a des contre-exemples, du coup je désespère un peu. :v

Du coup si quelqu'un aurait une piste... ce serait cool

merci

Ouais c'est ça, il faut avancer suivant l'ordre: on peut pas passer de A à C
et on peut rester 1 ou 2 jours dans une ville avant d'aller à la suivante

Le probleme dans ce que tu dis Blue c'est comment tu fais si ta derniere ville à le bonheur maximum

okiiii je vois
et dans le cas où il a entre 1 et 2 fois le nombre de pièces qu'il y a de villes tu mettrais les pièces en plus à la fin au début et suivrais le même raisonnement ?

merci beaucoup

Par exemple si tu as 9 pièces et que ton bonheur c'est 1 2 3 4 5 6 7 8 9 comment tu fais?

avec des bonheur comme 4 4 1 5 ou mon exemple precedent 1 2 3 4 5 6 7 8 9

up pls

Pour reformuler ce qu'a dit bluepoint, avec k pièces et n villes, on commence par essayer d'aller le plus loin possible (dis jusqu'à la ville n0), et ensuite on a deux choix :

• Soit on va jusqu'à la dernière ville. Dans ce cas-là, le meilleur score est obtenu en mettant les pièces en rabe sur les villes de poids maximal de manière gloutonne.
• Soit on ne va pas jusqu'à la dernière ville. Dans ce cas-là, on fait un appel récursif pour savoir quel est le score max avec k pièces en ne prenant en compte que les villes 1, 2, ..., n0-1.

Au final, le score maximal est donné en faisant un max entre ces deux valeurs.

Sur ton exemple : villes 4 4 1 5, avec 6 jetons.

• Soit on va jusqu'au bout, en mettant une pièce sur chaque ville (score 4+4+1+5), puis on met les deux pièces restantes sur les villes de poids maximum, donc +4+5. Score total 23
• Soit on ne prend pas la dernière ville, on fait un appel récursif avec l'ensemble de villes 4 4 1, toujours avec 6 jetons. Là comme il y a deux fois plus de jetons que de villes on répond immédiatement : (4 + 4 + 1)*2 = 18

Du coup, solution optimale = 23