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.
Version imprimable
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.
En passant ;)Citation:
Merci d'avance pour toute aide.
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
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 ...Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.Citation:
Envoyé par vttman
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]
Effectivement j'avais envisagée cette possibilité qui me permet de résoudre ce problème.Citation:
Envoyé par vttman
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.
J'essaye de comprendre ton raisonnement que veut dire a au rang k ?Citation:
Envoyé par pseudocode
Ca signifie qu'on a traité les "k" premiers éléments du tableau = résolu le sous-problème de taille "k".Citation:
Envoyé par Johnny P.
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:
2
3
4
5
6
7
8
9
10
11
12
13
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) ...
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.
7+4+4 ne respecte pas la contrainte "les éléments doivent être espacés de 3 cases" dans le tableau 4, 5, 7, 4, 5, 6, 4, 1Citation:
Envoyé par vttman
Il faut partir du principe qu'on a déjà résolu tous les problèmes de dimensions inférieures et ce demander comment on pourrait utiliser ces solutions pour résoudre le problème de dimension immédiatement supérieure.Citation:
Envoyé par Johnny P.
Pour ce problème, les dimensions qu'on a sont:
- n = le nombre d'éléments a sélectionner
- k = la taille de la liste
la distance min entre 2 éléments (d) est davantage une contrainte pour la sélection des éléments qu'une dimension du problème.
En tous cas, je n'ai pas vu de relation évidente entre un problème pour d=1,2 et le même problème pour d=3.
Maintenant, il faut construire les solutions des sous-problèmes.
C'est peut être plus simple si on représente cela comme un tableau qu'il faut remplir (Tableau à 2 dimensions n et k) :
Notre objectif c'est de trouver la valeur X (n=3 et liste complète = taille 8).Données: int[] a = {4, 5, 7, 4, 5, 6, 4, 1}; d=3 tableau des solution des sous-problèmes n,k: k= 1 2 3 4 5 6 7 8 ---------------------- n=0 | ? ? ? ? ? ? ? ? n=1 | ? ? ? ? ? ? ? ? n=2 | ? ? ? ? ? ? ? ? n=3 | ? ? ? ? ? ? ? X
Si la relation de récurrence n'est pas évidente dés le départ, on a toujours la méthode basique:
on commence avec les dimensions les plus faibles = on remplit progressivement le tableau de (0,0) jusqu'a (3,8).
si n=0, aucun élément à sélectionner, la solution est donc toujours 0.
si n=1, un seul élément à sélectionner => la solution est l'élément max dans la sous-liste de taille k
si n=2... aie! la contrainte de sélection (d=3) apparait => on ne peut pas choisir 2 éléments espacés de 3 cases tant que la sous-liste fait moins de 4k= 1 2 3 4 5 6 7 8 ---------------------- n=0 | 0 0 0 0 0 0 0 0 n=1 | 4 5 7 7 7 7 7 7 n=2 | ? ? ? ? ? ? ? ? n=3 | ? ? ? ? ? ? ? X
A partir de là, il nous faut une solution basée sur les cases déjà remplies du tableau.k= 1 2 3 4 5 6 7 8 ---------------------- n=0 | 0 0 0 0 0 0 0 0 n=1 | 4 5 7 7 7 7 7 7 n=2 | - - - ? ? ? ? ? n=3 | ? ? ? ? ? ? ? X
Qu'est ce que nous apporte le nouvel élément de la sous-liste (a[4]) pour le sous-problème de sélection de n=2 éléments dans une sous-liste de taille 4 ?
1. Rien. Ca ne va pas améliorer solution précédente => on va garder la solution pour n=2, k=3 (bon vu que c'est -infini, ca serait étonnant :D )
2. Ca nous permet de construire une meilleure solution => a[4] + un autre élément.
Cet autre élément doit être la "meilleure" sélection de 1 élément dans une sous-sous-liste dont tous les éléments sont à une distance minimum de d=3 par rapport à a[4].
=> c'est la solution d'un sous-problème connu: la sélection de n=1 élément dans la sous-liste de taille k=4-3=1 => la case n=1,k=1 du tableau
Et voila, on a l'esquisse de la relation de récurrence:
sol[2][4] = max( sol[2][3] , a[4] + sol[1][1] )
(reste à gérer proprement dans le code les cas où il n'y a pas de solution, c-a-d sol[i[j]=-infini, sinon l'addition va être fausse)
relation de récurrence qu'on peut généraliser en:k= 1 2 3 4 5 6 7 8 ---------------------- n=0 | 0 0 0 0 0 0 0 0 n=1 | 4 5 7 7 7 7 7 7 n=2 | - - - 8 ? ? ? ? n=3 | ? ? ? ? ? ? ? X
sol[n][k] = max( sol[n][k-1] , a[k] + sol[n-1][k-d] )
k= 1 2 3 4 5 6 7 8 ------------------------- n=0 | 0 0 0 0 0 0 0 0 n=1 | 4 5 7 7 7 7 7 7 n=2 | - - - 8 10 13 13 13 n=3 | - - - - - - 12 12