algorithme de factorisation en somme de nombre

Bonjour à tous

Je développe une appli en VBA et j'aurais besoin de retrouver toutes les solutions de sommes de termes d'un nombre plus grand. exemple :

Voici mes nombre sources:
48 50 51 52 54 56 57 58 60 62 63 64

Voici le nombre à factoriser : 321

Solutions :
- 2*64+58+3*45
- 6*45+51
- 5*54+51
...

si je ne me trompe pas, cela reviendrait à trouver les solutions de :
321 = a*48 + b*50 + c*51 + d*52 + e*54 +...
sachant que le nombre à factoriser n'est jamais un nombre premier.

J'avais commencé à faire un code du genre :
NbPv=321
Nsource(12)=(48,50,51,52,54,56,57,58,60,62,63,64)

pour j = 1 à 12
si NbPv/Nsource(12-j) > 0
NbNsource = entier(NbPv / Nsource(12-j))
NbPv = NbPv - NbNsource*Nsource(12-j)
FinSi
Suivant

Mais je me retrouve avec une partie entière qui me gène.

est ce que vous avez déjà eu à faire une factorisation en somme de termes?
Quelle méthode vous semble abordable?

Merci beaucoup pour votre aide!

Pierre

S'il n'y a pas beaucoup de chiffres et qu'ils sont petits, comme dans l'exemple, tu peut tout simplement essayer toutes les combinaisons.

Je ne sais pas s'il existe un meilleur algorithme, ça ressemble à un problème NP complet.

as-tu beaucoup de nombres sources?

Bonsoir,

Il y a environ 30 sources et les inconnues ne montent jamais au dessus de 20.

Effectivement, ça peut réduire les possibilités

Cordialement,

Pierre

ALors 30 c'est beaucoup... ton problème s'apparente à celui "du sac à dos":

http://interstices.info/jcms/c_19213...e-du-sac-a-dos

Si ton nombre cible N n'est pas "trop gros" par rapport à tes nombres sources Si, tu peux quand même faire une recherche exhaustive:

- tu tries tes Si par ordre croissant
- tu ne considères que les Si<=N, disons S1...Sp
- tu prends k=1+partie entière du max des N/Si
- tu testes tous les x1S1+...xpSp avec tous les xi<=k.

Effectivement, c'est le problème du sac à dos.

Merci de ton aide je vais voir ça!

Bonne journée

Cordialement,

pierre