Bonsoir developpeur, developpeuses.

Alors voilà je travaille sur la résolution du problème de sac à dos à l'aide de la programmation dynamique.
J'ai trouvé l'algorithme classique sur wikipedia (http://fr.wikipedia.org/wiki/Probl%C...tion_dynamique) et je l'ai implémenté.

Cependant j'aimerais l'optimiser en réduisant la consommation mémoire en O(n+W), n étant le nombre d'objets et W la capacité du sac (c'est aussi sur la page wikipedia que j'ai entendu parler de cette optimisation).
J'ai réfléchi a peu près deux jours sur ce problème sans rien trouver puis googlé deux autres jours toujours sans succès.

Ma question est simple, connaissez vous cet algorithme qui n'utilise que deux tableaux à une dimension, qui peut calculer le gain optimal et retrouver les objets utilisés pour atteindre ce gain ?

Dernière chose, l'optimisation mémoire en O(W) ne m'intéresse pas car je dois retrouver les objets mis dans le sac une fois le gain maximal calculé.

Merci.