Décomposition d'un nombre à partir d'éléments d'un ensemble

Bonjour,

Voici mon problème :

Imaginons qu'on ait un nombre x et un ensemble y de nombres.
Je cherche à obtenir toutes les décompositions possibles du nombre x enn additionnant les éléments de y.

Ma première idée a été d'utiliser un algo de type brute force sur l'ensemble y en calculant toutes les sommes possibles avec ses éléments et de sélectionner les calculs permettant d'obtenir x.

Cela fonctionne mais n'est pas forcément la meilleure solution.

J'aimerais donc avoir vos idées sur une meilleure approche afin de décomposer mon nombre x.

Merci d'avance de votre aide.

Bonjour,

si tu veux TOUTES les décompositions possibles, j'ai peur qu'un arbre de recherche s'impose.
En revanche si tu veux une décomposition, la meilleure selon certains critères, tu peux utiliser une heuristique : tabou, recuit simulé, ...

Le probleme est NP-complet, donc il n'y a rien de mieux de connu que la force brute a un facteur constant (qui peut cependant etre important!).

Bonjour,

Je pense qu'il existe tout un défi pour ce problème, c'est Génération des ensembles de nombre dont la somme est identique.

Cordialement,
Sidahmed

La question posée est un peu plus complexe que celle traitée dans le défi, mais qu'à cela ne tienne, elle a également déjà été traitée sur le forum. 8-)

--
Jedaï

Il serait sans doute efficace de mélanger un arbre d'exploration (pour avoir toutes les solutions) et la classique programmation dynamique du problème du sac à dos (pour savoir si dans une branche donnée au moins une solution existe).

Cela marche comme une branch-and-bound. Un noeud correspond à un sous-problème où on a décidé que certains éléments de y doivent être dans la somme et certains ne doivent pas l'être (les autres peuvent l'être ou ne pas l'être).
A chaque noeud, tu exécutes la programmation dynamique.

• Si tu ne trouves pas de solution ce n'est pas la peine d'explorer plus en profondeur le sous-problème.
• Si tu trouves une solution, tu choisis un nombre z dans y (parmi les nombres qui peuvent être ou pas dans la somme) et tu crées deux sous-problèmes: celui où z est dans la somme et celui où z n'est pas dans la somme.