Discussion :

[Johnny P.]

Bonsoir ,

Je désire résoudre le problème suivante avec la technique de la programmation dynamique avec mémoisation.
Mais je ne comprends pas très bien l'énoncé exactement , bien que j'ai compris que le but est de trouver la somme maximale cependant
la correspondance entre n et d n'est pas très clair dans mon esprit.

Si quelqu'un pourrait m'expliquer mieux cet énoncé ?

Merci d'avance.

[tbc92]

On va prendre le 2ème exemple. Tu as comme tableau 4.5.7.4.5.6.4.1
La disposition des nombres dans ce tableau est importante. Si on avait cet autre tableau 1.4.4.4.5.5.6.7, on aurait les mêmes nombres mais pas dans le même ordre, ce serait différent.

Et on te donne comme paramètres n=3, d=3
Il faut donc 'piocher' n=3 nombres dans ce tableau, et les distances entre les nombres doivent être d'au moins d=3.
Donc, si on prend le premier 4, tout à gauche, on ne peut pas prendre le 5 et le 7, mais on peut prendre le 2ème 4, etc

Sauf oubli, les différentes combinaisons qu'on peut prendre, c'est :
4.x.x.4.x.x.4.x --> 4+4+4=12
4.x.x.4.x.x.x.1 --> 4+4+1 = 9
4.x.x.x.5.x.x.1 --> 4+5+1=10
x.5.x.x.5.x.x.1 --> 5+5+1=11
La meilleure combinaison est donc la 1ère , elle rapporte 12 points.

Et l'objectif, c'est bien sur de trouver la meilleure combinaison, mais par programmation.

[Johnny P.]

Merci pour ta réponse , j'ai compris beaucoup mieux l'énoncé plus qu'à essayé de le résoudre.