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 ?=]
programmeur sur TI ^^

mon blog sur les TI => clic

mon (p'tit) fofo sur les TI => clic

2

3

rien

4

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

5

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 ... )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

6

Quand tu dis uniquement par additions, ça autorise de réutiliser deux fois le même nombre ou pas ? (une multiplication quoi tongue)
Je suppose que non mais on sait jamais cheeky
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

7

8

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 )

«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

9

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 ^^)
programmeur sur TI ^^

mon blog sur les TI => clic

mon (p'tit) fofo sur les TI => clic

10

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
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

11

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
Tout ce qui passe pas par le port 80, c'est de la triche.

12

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 wink

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)
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

13

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.
Tout ce qui passe pas par le port 80, c'est de la triche.

14

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...)
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

15

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

16

onur > heu je pense qu'il veut des coef entiers ..
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

17

les coefs peuvent être réels, je parle des variables.
Tout ce qui passe pas par le port 80, c'est de la triche.

18

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 )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

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 grin
programmeur sur TI ^^

mon blog sur les TI => clic

mon (p'tit) fofo sur les TI => clic

20


« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

21

C'est proche comme pbm, mais semble pas tout a fait identique non ?!
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

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)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

23

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 grin

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.
Tout ce qui passe pas par le port 80, c'est de la triche.

24

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"
Tout ce qui passe pas par le port 80, c'est de la triche.

25

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

Si, ./22

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

26

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 cheeky
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

27

pollux > ok.
Tout ce qui passe pas par le port 80, c'est de la triche.

28

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 ..

«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

29

Bah non j'ai changé pour minimiser la valeur absolue justement, d'où mon e >= truc et e >= -truc.
Tout ce qui passe pas par le port 80, c'est de la triche.

30

ha ok.
( valeur absolu c'est pas super linéaire mais bon si tu le dis ça doit marcher )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.