Discussion :

[Johnny P.]

Bonjour ,

J'essaye de résoudre ce type de problème à l'aide de la programmation dynamique mais je n'y parviens pas totalement.

Si quelqu'un aurait une aide afin que je parviens à trouver la solution ?

Merci d'avance pour toute aide.

Cordialement.

[vttman]

Merci d'avance pour toute aide.

En passant

Perso j'aurais déja ordonné le tableau
puis passé en fonction le tableau , un indice de départ (i), nombre , distance)

ex avec nombre = 2 et distance 3

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
i = 1
 
Appel de max ( mon tableau , i, 2, 3)
 
 
Fonction max ( ... )
{
<div style="margin-left:40px">Si i = 1 {
<div style="margin-left:40px">j'ordonne mon tableau</div>}
Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i 
Si Ok {
<div style="margin-left:40px">j'affiche mon résultat</div>} Sinon { 
<div style="margin-left:40px">i=i+1
max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)</div>}</div>}

Ainsi je traite 9 8 7 7 6 5 5 si rien 8 7 7 6 5 5 si rien 7 7 6 5 5 etc ...

[pseudocode]

Perso j'aurais déja ordonné le tableau

Le problème d'ordonner le tableau c'est que ca complexifie énormément la gestion de la distance minimale entre les éléments, ce qui est une contrainte du problème.
Sans compter que l'algo proposé devient alors une énumération des solutions possibles avec sortie au plus tôt (la première rencontrée étant la meilleure).

La solution purement dynamique que je vois c'est une variation du "Longest increasing subsequence problem", avec un historique des "d" derniers choix.
=> on maintien en mémoire "d" sommes partielles, suivant qu'on a sélectionné (ou pas) l'un des "d" derniers éléments.

Exemple pour d=3

si on a au rang k:
sum_00 = meilleure somme dans laquelle on n'a sélectionné ni a[k-2], ni a[k-1]
sum_01 = meilleure somme dans laquelle on a sélectionné a[k-1]
sum_10 = meilleure somme dans laquelle on a sélectionné a[k-2]

alors on aura au rang k+1:
new_sum_00 = max(sum_10 , sum_00) // meilleure somme dans laquelle on n'a sélectionné ni a[k-1], ni a[k]
new_sum_01 = sum_00 + a[k] // meilleure somme dans laquelle on a sélectionné a[k]
new_sum_10 = sum_01 // meilleure somme dans laquelle on a sélectionné a[k-1]

[Johnny P.]

En passant

Perso j'aurais déja ordonné le tableau
puis passé en fonction le tableau , un indice de départ (i), nombre , distance)

ex avec nombre = 2 et distance 3

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
i = 1
 
Appel de max ( mon tableau , i, 2, 3)
 
 
Fonction max ( ... )
{
<div style="margin-left:40px">Si i = 1 {
<div style="margin-left:40px">j'ordonne mon tableau</div>}
Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i 
Si Ok {
<div style="margin-left:40px">j'affiche mon résultat</div>} Sinon { 
<div style="margin-left:40px">i=i+1
max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)</div>}</div>}

Ainsi je traite 9 8 7 7 6 5 5 si rien 8 7 7 6 5 5 si rien 7 7 6 5 5 etc ...

Effectivement j'avais envisagée cette possibilité qui me permet de résoudre ce problème.

Mais , le but ici c'est de comprendre la technique algorithmique de la programmation dynamique.

Cette approche commence par une approche descendante par récursion avec mémoisation qui est pas si évidente.

Le problème d'ordonner le tableau c'est que ca complexifie énormément la gestion de la distance minimale entre les éléments, ce qui est une contrainte du problème.
Sans compter que l'algo proposé devient alors une énumération des solutions possibles avec sortie au plus tôt (la première rencontrée étant la meilleure).

La solution purement dynamique que je vois c'est une variation du "Longest increasing subsequence problem", avec un historique des "d" derniers choix.
=> on maintien en mémoire "d" sommes partielles, suivant qu'on a sélectionné (ou pas) l'un des "d" derniers éléments.

Exemple pour d=3

si on a au rang k:
sum_00 = meilleure somme dans laquelle on n'a sélectionné ni a[k-2], ni a[k-1]
sum_01 = meilleure somme dans laquelle on a sélectionné a[k-1]
sum_10 = meilleure somme dans laquelle on a sélectionné a[k-2]

alors on aura au rang k+1:
new_sum_00 = max(sum_10 , sum_00) // meilleure somme dans laquelle on n'a sélectionné ni a[k-1], ni a[k]
new_sum_01 = sum_00 + a[k] // meilleure somme dans laquelle on a sélectionné a[k]
new_sum_10 = sum_01 // meilleure somme dans laquelle on a sélectionné a[k-1]

J'essaye de comprendre ton raisonnement que veut dire a au rang k ?

[pseudocode]

J'essaye de comprendre ton raisonnement que veut dire a au rang k ?

Ca signifie qu'on a traité les "k" premiers éléments du tableau = résolu le sous-problème de taille "k".

Le principe de la programmation dynamique c'est d'utiliser les solutions des sous-problèmes (calculées précédemment) pour résoudre le problème actuel.

Mettons que j'ai déjà résolu les sous-problèmes:

{n=2 ; d=3 ; a=[4, 5, 7, 4]}
{n=2 ; d=3 ; a=[4, 5, 7, 4, 5]}
{n=2 ; d=3 ; a=[4, 5, 7, 4, 5, 6]}
{n=2 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}
et
{n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}

Comment je pourrais m'en servir pour résoudre le problème général:

{n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4, 1]}

Réponse:
A = j'ajoute la dernière valeur (1) à la solution du sous-problème {n=2 ; d=3 ; a=[4, 5, 7, 4, 5]}
B = je conserve la solution du sous-problème {n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}
la solution du problème général est max(A,B)


Si vous êtes fans des méthodes récursives:

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
int solution(int n, int d, int[]a, int k) {
  if (n==0) return 0;
  if (k>=a.length) return -INF;
 
  int s0 = solution(n-1, d, a, k+d);
  int s1 = solution(n,   d, a, k+1);
 
  if (s0==-INF) return s1; else return Math.max(a[k]+s0,s1);
}
 
int[] a = {4, 5, 7, 4, 5, 6, 4, 1}; int n=3, d=3;
int max = solution(n,d,a,0);
//

[vttman]

Effectivement Pseudocode ...
Pour du code concis ça l'est !
=>
BRAVO

Une remarque cependant... pour n = 3 et d = 3, ton code Java me renvoie 12 ?
Sauf erreur de ma part (une des dernières sans doute sur 2017), je m'attendais à 15 (7+4+4) ...

[Johnny P.]

Merci pseudocode ton code fonctionne et ce pour tous les cas , il me faudrait beaucoup d'entrainements pour arriver à trouver une solution si élégante...
ton code est plus compacte.

As-tu des conseils pour arriver à maitriser cette technique , livre à me conseiller etc...? car elle me semble assez complexe et encore ce type de problème n'était pas des plus difficiles.