Complexité des algorithmes

par **momento85** » 15 Sep 2009, 10:23

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.

par **Clembou** » 15 Sep 2009, 12:34

Oui, et alors ? :hein:

Complexité des algorithmes

complexité des algorithmes

Qui est en ligne