Discussion :

[zamato]

Bonjour.

J'essaye depuis quelque temps d'apprendre les rudiments de la programmation dynamique, j'ai lu quelques tutoriels et plusieurs exercices (d'ailleurs si vous avez de bons liens à me conseiller ça m'aiderait). Ya un exercice qui me bloque :

On a une séquence de N poids (nombres entiers). On doit les répartir de part et d'autre d'une balance, de façon à ce que la balance soit parfaitement équilibrée.
Il faut que la somme des poids à gauche soit égale à la somme des poids à droite. De plus il faut maximiser la somme des poids que l'on met sur la balance, on n'est pas obligé d'utiliser tous les poids bien sûr.


Je sais que ce problème est connu sous le nom de "2-partition problem", je sais le résoudre lorsqu'on doit utiliser tous les poids, et qu'il suffit de minimiser l'écart entre les deux partitions, mais pour cette version...je vois pas! Merci de votre aide future.

[Franck Dernoncourt]

Un bon cours en PJ. Hésite pas à nous faire part des liens/docs que tu as trouvés intéressants !

[zamato]

Merci pour ton lien, je l'ai lu en entier c'est vrai qu'il est bien (j'ai bien aimé le fait qu'il parle des fonctions mémoires), mais je connais déjà les concepts qui y sont présentés ainsi que les exemples. Je ne suis pas rentré dans le détail des démonstrations car c'est un peu trop compliqué, et je cherche plutôt à résoudre divers problèmes.

Un tuto avec quelques exemples et un des exercices résolus par vidéos.

Si quelqu'un a des suggestions, des idées d'exercices ou veut partager ses connaissances sur le sujet il est le bienvenu.

PS : Je n'ai toujours pas de solutions pour le problème que j'ai posé dans mon post précédent.

[Artix]

Bonsoir,

d[N][K] = max(max(d[N-1][K-v[N]]+v[N], d[N-1][K+v[n]]+v[N]), d[N-1][K])
Où N est l'indice du poids, et K est le déséquilibre à gauche.
Au départ, d[0][0] = 0 et d[0][1..2*somme de tous les poids] = +INF
Il faut faire attention aux bords (s'arranger avec le *2 pour ne pas avoir d'indices négatifs).
d[N][0] contiendra la somme max de poids tels que la balance soit équilibrée.

Pour être plus clair, on peut voir ça comme un graphe implicite.
Un noeud : {l'indice du poids, le déséquilibre à gauche}
Un arc : Il y en a 3 : soit on met le poids à gauche (poids +v[N]), soit on met le poids à droite (poids +v[N]), soit on ne le prend pas.
Graphe orienté et acyclique donc un peut dynamiser, et on veut le poids max.

Jules.

[zamato]

Salut.

Merci pour ta réponse, en effet vu comme ça, ça parait simple... (Par contre on ne devrait pas initialiser d[0][1..2*S] à -INF plutôt qu'à +INF?).
Tu aurais pas quelques autres petits exos de progdynamique, pour que je puisse m'améliorer un petit peu?

PS : Je trouve que la 2e partie de ton message est moins claire que la 1ère (mais j'ai quand même compris ce que tu voulais dire.)