Bonjour,
J'ai un problème, je n'ai pas beaucoup de connaissances en algo, et je ne sais pas comment faire pour resoudre ce problème... je demande juste une idée d'une technique pour me lancer et non le code bien sur, j'irais me renseigner après et faire travailler mes neurones.
Mon problème : j'ai :
-> un vecteur A qui contient 17 entiers. Ils peuvent etre vu comme le nombre d' "occurences" de l'exercice i (i entre 0 et 16 donc).
-> un vecteur B qui contient aussi 17 entiers. Il peut etre vu comme étant l'estimation du temps pour faire une occurence de l'exercice i.
On peut donc estimé le temps qu'il faut pour réaliser le vecteur A : somme pour i de 0 à 17 de A[i]*B[i].
Or il faut que cette somme soit egal, à un facteur F près, à TempsTotal.
On se trouve dans le cas ou le temps estimé > temps total.
Je dois donc faire un algorithme pour enlever des occurences de A, afin de diminuer le temp estimé. Je ne cherche pas la solution optimum, mais une solution qui marche (au facteur F près, cad (100-F)*TempsTotal < temps < (100+F)*TempsTotal.
Contrainte : on ne peut enlever que des occurences pour des exercices qui sont dans une liste de candidats liste_candidats (taille variable).
 
C'est possible en recursivité ? je me casse le crane la  

Les données sont différentes mais je pense que la méthode reste valable : utiliser un algo génétique. J'en avais mis un au point pour optimiser la gravure de Cd. J'avais un nb de CD à graver avec des fichiers pris parmi une liste donnée. Je ne suis donc pas obliger de prendre tous les fichiers dans le cas où la somme des fichiers > somme des Cd vierges (des 700 ou des 650 mo).
http://forum.hardware.fr/hfr/Progr [...] 4853_2.htm
 
Pour plus de détails, cf mon site perso : http://chris-jav.servhome.org/projects_optcd.php

chuis d'accord qu'expliqué sous forme de CD est autrement plus facile à comprendre pour moi.
 
comment j'y pannais rien les premières lignes

Normal, t'étais trop fatigué suite au temps passé à optimiser ton crible en C#

En fait, l'utilisation d'un algorithme génétique ne me semble pas justifié dans ton problème. D'après ce que j'en ai compris, on se trouve dans un cas ou les variables sont indépendantes les unes des autres. Cela signifie qu'on peut se permettre de les traiter séparément, une après l'autre, tout en étant sûr de converger vers la solution optimale. La seule contrainte serait de les traiter dans l'ordre de temps décroissant afin de faire en premier les "grosses" modificaion dans la somme finale. Dès que le delta-t pour une variable donnée devient trop grand, tu passes à celle de temps inférieur.
Tu devrais pouvoir trouver la solution optimale en temps linéraire.. (ou alors j'ai rien compris à ton problème)

Classer les "jobs" suivant l'ordre décroissant de leur temps d'exécution est l'algo LPT (en ordonnancement). Pour ce type de pb, ça ne suffit pas à donner l'optimum (par contre, ça te donne une solution possible). Après  que tu partes de cette 1ère solution pour l'améliorer, pourquoi pas. Mais tu n'expliques pas quel algo tu appliques pour améliorer...
Le hic dans ce type de pb énoncé, c'est que tu n'es pas obligé de prendre tous les jobs : tu peux en prendre x parmi N jobs...
 
A moins que l'état de l'art est évolué depuis 2002 et qu'un algo ait été trouvé pour donner la solution exacte, il n'existe que des heuristiques à ma connaissance. Une heuristique à base d'algo génétique est la plus simple à mettre en oeuvre et donne de bons résultats ; on peut même optimiser l'algo en établissant des tables de paramétrage de l'algo suivant l'ordre de grandeur des 2 paramètres d'entrés (le nb de fichiers et le nb de Cds).  
Après, on peut se rabattre aussi sur de la programmation dynamique, mais je trouve que c'est plus dur à coder...

Effectivement, l'approche que j'ai décrite ne garanti pas la solution optimale. C'est en fait une approche gloutonne qui pourrait très bien ne pas donner de solution pour certaines instance du problème.
 
En fait, le problème décrit est équivalent au problème du sac à dos non? dans ce cas , il y un article wikipedia assez bien fourni sur sa résolution et effectivement, on peut trouver la solution optimale par programmation dynamique.

c'est une variante du sac à dos dans ce sens qu'il y a bien la notion de poid mais il n'y a pas de valeur (où alors, toutes les valeurs des objets sont égales).
Et l'algo dont je parlais est décrit dans wikipedia comme étant l'algo génétique élitiste (on garde le meilleur individu de la population)