Discussion :

[nediam]

Bonjour,

Comment procéderiez vous pour connaitre les combinaisons de prix d'articles (disponibles en base de données) pour arriver à un montant donné.

Exemple, que puis-je acheter pour arriver à la somme exacte de 101,34 euros, le script me sortirait : soit par exemple un article de 101,34 euros, ou un produit de 50,10 + 51,24 ou 3 articles etc.... le tout sur une grosse base de données, cependant seule 2 ou 3 combinaisons suffisent à la fin...

Merci de votre aide

[random]

dans une base de données ce n'est pas trop facile à traiter

on règle en général les problèmes de combinaisons par le produit cartésien
de valeurs issues de deux tables

j'attire ton attention sur le fait que s'agissant de recherche combinatoire les
requêtes intermédiaires seront de tailles énormes avec des temps de calcul très longs

[Mac LAK]

Cela ressemble furieusement au problème du sac à dos, ton truc, non ?

[Invité]

Pas tout à fait, dans le problème du sac à dos, on cherche à maximiser une variable (valeur des objets mis dans le sac), sous une contrainte inégalité (contenance du sac).

Ici, le but est de trouver, dans une liste de nombres (avec? sans répétitions?) tous les sous ensembles (avec ou sans répétition, éventuellement avec un nombre maximal de répétitions) ayant une somme donnée.

Dans la littérature anglophone, ce problème est connu sous le nom de Subset Sum Problem (problème des sommes de sous ensembles). Il est apparemment difficile. On en connait des solutions en temps exponentiel ( 2^(n/2) ), mais pas mieux. Apparemment, prouver qu'il existe des solutions en temps polynomial reviendrait à prouver P=NP... C'est pas gagné!

Pour les anglophones, il y a de l'info là
http://en.wikipedia.org/wiki/Subset_sum_problem


On va donc devoir chercher une solution énumérative. Personnellement, je commencerais par construire une liste de "petites valeurs" faisables et infaisables (en combinant les produits 'pas chers'). Cela va simplifier la recherche ultérieure.

Puis je partirais du nombre, en ajoutant des articles à la liste, par ordre de prix décroissant (les plus chers d'abord). Dès qu'on atteint un "nombre faisable" de la liste précédente, on a une solution, dès qu'on atteint un infaisable, on élimine cette solution partielle.

Les SGBD ne sont clairement pas l'outil qu'il faut pour ce genre de problème.

Francois

[random]

il s'agirait peut être de préciser "seule deux ou trois combinaisons suffisent à la fin"

sinon avec une base de 10 ou 15 mille articles bonjour les temps de calcul

[Invité]

Ca dépend, en fait...

Si on a beaucoup d'articles, mais des "montants totaux" pas trop élevés, ca va assez vite (parce qu'un montant, c'est 2 ou 3 articles, donc même avec 10000 articles 1e8 à 1e12 possibilités, énumérable...)

Si on a peu d'articles et des montants élevés, pas de pb non plus...

Si les articles sont nombreux, et que les montants sont élevés, là alors...

Francois

[Nemerle]

tu tries tes prix par ordre croissant et tu construis au fur & à mesure l'arbre de tes possibles...