Envoyé par
vttman
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) ...
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, 1
Envoyé par
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.
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.
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) :
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
Notre objectif c'est de trouver la valeur X (n=3 et liste complète = taille 8).
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
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
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 4
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
A partir de là, il nous faut une solution basée sur les cases déjà remplies du tableau.
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 )
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)
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
relation de récurrence qu'on peut généraliser en:
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
Partager