Le problème 0-1 où la valeur est égale à Knapsack poids NP-complet?

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?

Answer 1

Oui, on appelle cela le problème sous-somme et est NP- dur.