Bonjour,
Afin de montrer que le problème du sac à dos est un problème NP-complet, j'ai vu qu'il fallait montrer :
- qu'il s'agit d'un problème NP : fait
- qu'un autre problème NP-complet lui est polynomialement réductible. c'est la que j'ai des difficultés.
J'ai lu à plusieurs reprise qu'en partant du problème de partition (qui consiste à partager un ensemble d'entiers en 2 sous ensembles de même somme) et en montrant qu'il s'agit en fait d'un cas particulier du problème du sac à dos, cela suffirait. Or selon moi il faudrait montrer que partition est réductible à sac à dos et qu'ici on montre le contraire...
Merci de vos réponses.
-----