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.