Le problème 0-1 où la valeur est égale à Knapsack poids NP-complet?
-
16-10-2019 - |
Question
J'ai un problème que je pense est NP-complet. Il est facile de prouver qu'il est NP. Mon train courant de pensée tourne autour de l'utilisation d'une réduction de havresac mais il entraînerait des cas de 0-1 avec la valeur Knapsack de chaque élément étant égale à son poids.
Est-ce toujours NP-complet? Ou suis-je manque quelque chose?
La solution
Oui, on appelle cela le problème sous-somme et est NP- dur.
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange