approche - Page 3

OK. On a pensé exactement à la même solution

c'est pas pour vous décourager mais vous êtes en train d'essayer de prouver P=NP

le pb du sac à dos est http://en.wikipedia.org/wiki/Fixed-parameter_tractable en ce sens que si on fixe N (nombre voulu dans la notation de ./1) le problème est polynomial, mais si N peut être quelconque il n'y a pas d'algo polynomial à moins que P=NP.

pour la méthode d'onur c'est pas encore ça mais en continuant dans cette direction on devrait retomber sur la programmation dynamique ^^ (qui passe par un tableau au lieu d'appels récursifs pour éviter d'appeler plusieurs fois la fonction avec les mêmes arguments)

J'ai rien compris à ton message, perso

si N=42, quel que soit le nombre n de nombres à additionner on peut résoudre le pb en O(n) opérations (le 42 influence juste la constante du O).
mais si N=10^n, on sera incapables de résoudre ça en temps polynomial en n, bien que la description du problème tienne encore sur O(n) bits... (la raison c'est qu'avec des N super élevés on peut encoder d'autres problèmes NP-complets comme 3-SAT, chose impossible si on se restreignait à N faible)

Thibaut > http://en.wikipedia.org/wiki/P%3DNP si tu ne sais pas à quoi Pollux fait référence ^^

(en deux mots : P est l'ensemble des problèmes solubles par un algorithme classique Polynomial (cf. ma définition plus haut ^^), tandis que NP est l'ensemble des problèmes solubles en temps Polynomial par un algorithme Non-déterministe. Le problème consiste à savoir si ces deux ensembles sont égaux, à savoir si tout problème soluble en temps polynomial par un algo non-déterministe peut nécessairement aussi l'être par un algo déterministe. On pense que ce n'est pas le cas mais ce n'est pas prouvé.

On définit ensuite les problèmes NP-complets, ce sont des problèmes NP dont il est prouvé que s'ils appartiennent à P, alors tous les autres problèmes NP aussi. La méthode classique pour prouver qu'un problème est NP-complet est de se ramener à un autre problème NP-complet connu : montrer que si on avait un algo déterministe polynomial permettant de le résoudre, il serait possible à partir de cet algo d'en construire un autre, également polynomial, qui résout le problème connu.

Actuellement quand un problème est NP-complet les seuls algorithmes déterministes qu'on arrive à trouver pour le résoudre sont exponentiels, enfin il me semble.)

./62 > Non je suis conscient de se ce que je fais J'ai pas cité de complexité en n². j'ai parle de nlogn pour le tri du début. Et oui, mon but est de tomber sur de la prog dynamique mais bon on va pas lui faire tout le boulot non plus, il a les éléments nécessaire pour comprendre la philosophie du truc et finir tout seul

Merci Pollux, et Sally pour tes "deux mots" très détaillés