Bonjour!! Tu es nouveau sur le forum. Je te prie d'aller lire le réglement du forum avant de poster, et de le respecter!
Considérons le problème du sac à dos sous la forme suivante:
(P):"étant donné n+1 entiers positifs c1,c2,...,cn et K ,existe -il un vecteur x de {0,1}^n tel que : somme (Cj Xj) =K avec j=1...n ? "
Montrer que le problème (P) appartient à la classe NP.Pour cela on décrira soigneusement un codage des données du problème ,on évaluera la taille de ce codage et on exhibera un algorithme non déterministe.