approche - Page 1

b'jour ! je suis a la recherche d'une idée pour un algo : une fonction qui prendrait une liste de nombres en argument et un nombre N, et qui, en utilisant la liste de nombres, uniquement par additions, s'approche le plus possible de N (c'est p'tet pas assez clair?). Quelqu'un a une idée ?=]

rien

A première vu, c'est un problème exponentiel ça, non ?
Ta liste est grande tama ? Si oui, ça va prendre du temps sur une TI.

C'est clairement NP-complet, t'auras que des algos de merde. (enfin .. )
Sinon y'a des heuristiques qui marchent pas trop mal .. ( genre tu prends le plus grand nombre plus petit que la difference qui reste a combler ... )

Quand tu dis uniquement par additions, ça autorise de réutiliser deux fois le même nombre ou pas ? (une multiplication quoi )
Je suppose que non mais on sait jamais

Si vu que c'est NP-complet, fondamentalement y'a pas mieux que de tout essayer ( à un facteur constant près .. ). Son histoire c'est le truc de rendre la monaie ..

(sinon il faut pas aboutir au resultat -ça marchera pas dans tous les cas .. -, il faut s'en approcher le plus possible )

thibaut>bah je sais pas ce que t'appelles grand, une dizaine quoi ; GC>non (désolé pour la présentation, j'écris sur un portable ^^)

very (./8) :
Son histoire c'est le truc de rendre la monaie ..

J'aurais plutot dit "le compte est bon" avec que des additions, et en effet c'est du NP complet, mais ça dépend de la liste de nombre... Si ce ne sont que des puissances de 2 par exemple (ou de 3, 4 & co) il doit y avoir moyen de faire un algo non NP complet

C'est un PLNE:

soit V = {v1,v2,v3...vn} ta liste en entrée
variables: x1,x2,x3..., xn
avec x1: je prends le 1er nombre
x2: je prends le deuxieme, etc..

tu veux:

Minimiser e
sous

e >= (N - v1*x1 - v2*x2 - v3*x3 ... - vn* xn)
e >= - (N - v1*x1 - v2*x2 - v3*x3 ... - vn* xn)


x1,x2,.... xn appartenant à l'ensemble des entiers.

tu mets ca sous la forme

A*X <= B, si A est une matrice totalement unimodulaire, tu n'as pas besoin de forcer les xi à entier (et ca resoudra en temps polynomial)

edit: si on ne peut pas prendre deux fois un meme élément de la liste, alors c'est x1,x2,... xn appartenant à {0,1} autrement dit on est sur un hypercube de dimension n

onur (./11) :
A*X <= B, si A est une matrice totalement unimodulaire, tu n'as pas besoin de forcer les xi à entier (et ca resoudra en temps polynomial)

Elle ne l'est pas

et mettre le problème sous cette forme revient à utiliser un programme externe pour résoudre le problème (genre glpk, lp_solve ou cplex qui est le meilleur même s'il coûte la peau des fesses)

Oui derriere faut utiliser une lib, pour ca faudrait savoir si c'est oncalc ou onPc qu'il veut faire ça.

Sinon il doit y avoir des trucs standalone écrits en C qui font du simplex et des résolutions dans {0,1}^n.

onur (./13) :
Sinon il doit y avoir des trucs standalone écrits en C qui font du simplex et des résolutions dans {0,1}^n.

mais faut voir les perfs qu'il y a (et sur calc, on peut oublier...)

Faut voir la longueur de la liste aussi, si c'est une liste de 10 ou moins de nombres, et on ne peut pas prendre le même nombre plusieurs fois (donc on a le choix que de prendre ou ne pas prendre) alors essayer toutes les possibilités ne prendra que 1024 essais. Mais plus la liste est longue, plus l'effort exponentiel se fera remarquer.

onur > heu je pense qu'il veut des coef entiers ..

les coefs peuvent être réels, je parle des variables.

J'appelais coef ce que tu appelle "variable" (je pense que sont nombres originaux sont entiers ou de toute faç retionels, et qu'il veut ajouter 0/1 fois chacun )

alors,
1. oui, il n'y a pas beaucoup d'éléments, une dizaine environ
2. on ne peut pas utiliser plusieurs fois un nombre, c'est le prendre ou ne pas le prendre
3. j'ai pas compris vos histoires

C'est proche comme pbm, mais semble pas tout a fait identique non ?!

Ben si, c'est la version 0-1 avec poids=valeur.

(si c'est juste "une dizaine" et pas "deux dizaines" et que ça a pas besoin d'être performant, le bruteforce en 2^n peut faire l'affaire)

Oui knapsack lui ressemble mais c'est pas la même forme.

tama (./19) :
alors,
1. oui, il n'y a pas beaucoup d'éléments, une dizaine environ
2. on ne peut pas utiliser plusieurs fois un nombre, c'est le prendre ou ne pas le prendre
3. j'ai pas compris vos histoires

1° Ok, en listant toutes les possibilités tu devrais pouvoir t'en sortir, mais entre 10 et 11 éléments y a une grosse différence déjà. 1024 additions à faire pour 10 éléments en entrée, et 2048 pour 11 éléments.

2° ok, donc les variables (les x1,x2,...,xn) seront dans {0,1} (et je dis bien {0,1} pas [0,1])

3° En fait, c'est un problème linéaire d'optimisation. Il existe des outils (et des algorithmes) tout prets qui peuvent résoudre des problèmes du genre:

Minimiser (Expression)
sous les contraintes: (suite d'expression)

il faut que les "expression" soient linéaires. Ici tes variables de décision sont les x1,x2, .. xn que j'ai cité. Tu balances ça à un outil:

Minimiser N - v1*x1 - v2*x2 ... - vn*xn
sous (rien)

et tu dis à l'outil que tu veux que x1 soit 0 ou 1, pareil pour les autres xi.
et donc l'outil te sortira la combinaison qui minimise la différence entre la somme et N. Sauf que ça, il va te mettre tous les xi à 1 pour avoir l'expression N - v1*x1 - v2*x2 ... - vn*xn la plus petite possible. Donc il faut "feinter". Tu passes par une variable supplémentaire e, qui representerait la valeur absolue de N - v1*x1 - v2*x2 ... - vn*xn

donc le programme devient:

Minimiser e
sous:
e >= (N - v1*x1 - v2*x2 - v3*x3 ... - vn* xn) 
e >= - (N - v1*x1 - v2*x2 - v3*x3 ... - vn* xn) 

xi appartenant à {0,1}

si tu veux pas que la somme dépasse N, il faut mettre

Minimiser e
sous:
e >= (N - v1*x1 - v2*x2 - v3*x3 ... - vn* xn) 
e >= 0
xi appartenant à {0,1}

donc:
1° tu veux que la somme puisse dépasser N ou pas?
2° tu as surement des outils écrits en C qui résolvent ça, une fois que tu as explicité ton problème sous cette forme (comme quelqu'un l'a dit il faut voir la perf oncalc aussi)
3° sans s'occuper de cette forme, on peut pondre un algorithme branch&bound qui peut éviter de lister les 2^n possibilités.

y a meme une version javascript qui peut résoudre ce genre de problème: http://people.hofstra.edu/Stefan_waner/RealWorld/simplex.html
click sur "example" puis "solve"

onur (./23) :
Oui knapsack lui ressemble mais c'est pas la même forme.

Si, ./22

Pollux (./22) :
Ben si, c'est la version 0-1 avec poids=valeur.

(si c'est juste "une dizaine" et pas "deux dizaines" et que ça a pas besoin d'être performant, le bruteforce en 2^n peut faire l'affaire)

Vu comme ça

pollux > ok.

onur (./23) :
3° sans s'occuper de cette forme, on peut pondre un algorithme branch&bound qui peut éviter de lister les 2^n possibilités.

Le simplex dans le pire des cas théorique ça peut faire du exponentiel. Sinon il disait "le plus proche" (en valeur absolu) et là t'as changé un peu le problème (le plus proche en étant au dessus ). Bon faudrait le faire deux fois quoi ..

Bah non j'ai changé pour minimiser la valeur absolue justement, d'où mon e >= truc et e >= -truc.

ha ok.
( valeur absolu c'est pas super linéaire mais bon si tu le dis ça doit marcher )