Discussion :

[korn900]

Le probleme que je dois resoudre est le suivant :
Etant donne un ensemble de n valeurs qui sont donnees, peut-on former exactement le total t avec une combinaison de ces valeurs ?

La seule methode possible pour resoudre le probleme (a mon avis) est de lister toutes les possibilites (on peut en eliminer si des valeurs donnees se repete par exemple..).

Les differentes solutions que j'ai trouver pour resoudre le probleme sont :

1-Methode recursive
- on considere une valeur i ( note val[i] )
- les combinaisons possibles sont celles ou val[i] est selectionne et celles ou val[i] n'est pas selectionner
- on utilise donc la fonction suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
bool fonction ( int i, int sous_t )
 if(i == 0) return (sous_t == 0 || sous_t - val[i] == 0);
 if (sous_t == 0)
   return true;
 else if (fonction(i-1,sous_t - val[i]) == true)
   return true;
 else if(fonction(i-1,sous_t) == true)
   return true;
 else
   return false
}

- le premier appelle est fait avec fonction(n,t) n correspont au nombre de valeurs et t au total que l'on souhaite obtenir

2-Methode iterative
Principe :
Si 0 est l'etat non selectionner est 1 l'etat selectionner d'une valeurs, toutes les combinaisons possibles sont les nombre binaires allant de 0 a n(en binaire), si necessaire on complete le nombre binaire par des 0 au debut pour obtenir un nombre a n chiffres.
- la methode peut etre ameliorer en triant les valeurs et en ne selectionnant pas de valeurs + grandes lorsqu'on depasse le total.

Mon probleme est que c'est 2 methodes ne sont pas assez rapide. La fonction recursive est forcement tres lente, et dans ma methode iterative, je n'ai pas trouver de facon tres 'simple' de compter en binaire.
Je voudrais savoir quelles autres algo peuvent etre implementer ? Comment utiliser la programmation dynamique en stoquant des resultats ?

J'ai penser a stocker les possibilites avec 1 valeur {0, 1 }, puis d'essayer la 2 eme valeurs sur toutes les possibilites a 1 valeurs qu'on a trouver en continuant a sotcker les possibilites(ce qui donne : { (0,0);(0,1);(1,0);(1,1) }, apres essayer la 3eme valeurs sur les possibilite qu'il y avait a 2 valeurs { (0,0,0);(0,0,1);(0,1,0);(0,1,1);(1,0,0);(1,0,1);(1,1,0);(1,1,1) }etc...
La quantite de valeurs sauvegardees va tres vite devenir enorme..

Je sais que ce sujet a deja ete aborde de nombreuses, mais je n'ai pas trouve de reponse satisfaisante.
Je voudrais aussi savoir si ce probleme correspond bien a celui du 'bin packing' , je pensais que oui et j'ai cru comprendre que le pour le bin packing on s'interesse a minimiser le nombre de boite differentes (de capacite t) ? l'algorithme FFD (first fit decreasing je crois) ne peut pas s'appliquer a mon probleme ?

[Jedai]

Ce problème est classiquement connu sous le nom de subset-sum et est (désolé pas d'algorithme simple, comme tu l'avais pressenti d'ailleurs) NP-complet...
Pour un résumé des meilleurs algorithmes de résolution ou d'approximation, voir cette page.

--
Jedaï