Bonjour,

Dans le but d'écrire l'algorithme de programmation dynamique qui résoud le problème, suivant, je souhaite établir la relation de récurrence adéquate.
On considère une route droite d’une longueur de K kilomètres sur laquelle on cherche à placer des antennes relais de TV. Les sites disponibles sont caractérisés par les entiers x1 , x2 , . . . , xn où les xi représentent la position, en kilomètres, des antennes le long de la route (0 ≤ xi ≤ K). De plus, une antenne placée à la position
xi génère un revenu de ri (0 ≤ i ≤ n). La distance entre deux antennes successives ne peut être inférieure ou ́égale à 5 km. Combien et où devez-vous placer vos antennes afin de maximiser vos revenus.

Voici la relation de récurrence que j'ai écrit:
les paramètres variables sont:
k: la longeur de la route,
xi: la position de l'antenne
xi-x(i+1) > 5

Il s'agit ici de maximiser le nombre d'antennes à placer. De ce fait, soit N le nombre d'antennes à placer. Alors N varie en fonction de k et xi.
Tout d'abord, si la première antenne est placée à la position xi, il reste alors k km sur lesquels il est possible de placer des antennes. L'antenne suivante à placer le sera à la position 5+xi ; il restera alors k-5-xi km km sur lesquels il est possible de placer des antennes.
Si je décide de ne point planter d'antenne à la position xi, alors je peux en planter à la position 5+xi.

D'où ma relation de récurrence suivante :
N(k, i) = max(Nxi, k) + N5+xi, N(xi, i-n) && N(xi, i-n)

Est ce juste ? Merci.