c'est quoi l'algorithme du sac à dos ?

regarde sur wikipédia le problème du sac à dos.
notre probleme revient a implementer cet algo a utilisant comme
contenance du sac --> somme des valeur de piece /2
valeur d'un poids(a mettre dans le sac) --> valeur de la piece.
contrainte:
la soe des valeurs a mettre des pieces a mettre dans le sac est de N/2.
N étant le nbre de piece total.

Si l'on le voit comme ça, si l'on remplie un sac de manière optimal avec N/2 pieces alors l'autre sac contiendra forcement le reste des pieces et sera optimal aussi.

J'espère que mon raisonnement à été bien exprimé, nous attendons toute autre proposition.

l'idée est pas mauvaise ....
mais pour remplir un vecteur tu vas faire comment ?
essayer toutes les possibilités et regarder l'optimale ?
ça retombe sur ce que nous étions en train de faire avant :s
sauf que maintenant tu travailles avec 1 vecteur et plus 2 ...
pas un grand gain :s

je vais essayer de combiner ton idée précedente avec le sac a dos

si tu lis bien des tutos sur ce pb tu verra que ça complexité s'exprime de maniere polynomiale ce qui rend le pb plus facile a denombrer.

wais en fait j'avais commencé puis j'en ai eu marre
je verrai ça une autre fois
mais polynomiale-ment °_0 je vois pas comment faire °_°

regarde ce lien:
http://fr.wikipedia.org/wiki/Probl%C3% [...] lution_exacte

C'est pas exactement l'algo que proposait Maholmar par hasard?