Toutes les combinaisons de répartition de n éléments dans n containers

Bonjour, mon problème est le suivant: dans un système de facturation, permettre d'utiliser des avoirs qui permettront de ne pas payer la facture. Mais ceci avec des contraintes :

• On a une et une seule facture composée de un à plusieurs articles ayant un montant (sans notion de quantité 1 ligne = 1 article)
• On a un à n avoir composé d'un montant

Le but est de trouver si un ou plusieurs avoirs peuvent-être utilisés sachant que :

• Toutes les lignes d'articles doivent être répartis entièrement dans des avoirs. Ainsi la facture sera à 0
• Un article doit être utilisé entièrement dans un avoir. On ne peut pas mettre une partie du montant dans un avoir et une autre partie dans un autre avoir

Par exemple :
Facture avec 3 articles : 100, 200 et 300€.
- avec 2 avoirs de 500 et 100€ : c'est bon car 500 = 200 + 300 et 100 = 100
- avec 2 avoirs de 250 et 250 : c'est pas bon car on ne peut pas répartir entièrement les articles dans les avoirs sans les scinder

L'idée est donc d'obtenir toutes les combinaisons possibles de n articles dans n avoirs puis de regarder si la somme des articles disposés dans un avoir est égale à l'avoir. Toujours avec l'exemple ci-dessus:

Avoir 1 500€	Avoir 2 100€
100	200 + 300
100 + 200	300
100 + 300	200
200	100 + 300
200 + 100	300
200 + 300	100
300	100 + 200
300 + 200	100
300 + 100	200

Ce qui me manque c'est l'algo qui va permettre d'obtenir ces combinaisons. Merci si quelqu'un peut m'aider

C'est le problème du sac à dos, en anglais : Knapsack problem.
Une recherche dans ton moteur de recherche préféré te donnera énormément d'infos.

Bonjour et merci de cette réponse. En effet il s'agit du problème du sac à dos. Mais si on trouve pas mal de choses pour résoudre la répartition dans un sac en revanche presque plus rien concernant la répartition dans plusieurs sacs car c'est le cas qui m'intéresse. En revanche je n'ai qu'un critère alors que dans les pages trouvées sur internet il est question de poids et valeurs. Alors ça devrait être plus simple avec un seul critère mais je ne sais pas comment l'adapter à plusieurs sacs.
Oui on trouve bien des formules mathématiques mais qui ne m'aide pas beaucoup car ce que je désire c'est l'implémenter en java et mes math ce sont comme envolées...

Merci en tout cas

Si le nombre de prix est faible et le nombre d'avoirs est faible, alors lister toutes les combinaisons possible est envisageable.

Commence par un seul avoir et tente de trouver toutes les combinaisons de prix dont la somme fait exactement cet avoir.
Pour l'avoir suivant, retire de la liste les prix déjà utilisé et recommence.

Maintenant, comment faire toutes les combinaisons : fonction récursive, en paramètre : l'avoir restant, la liste tab_prix des prix, la liste tab_bool de booléen pour dire si le prix est utilisé ou pas, indice i du prix à verifier
condition d'arrêt : si avoir = 0, alors vrai, sinon si avoir < 0 alors faux sinon si i atteint fin tableau alors faux
avoir = avoir - tab_prix[i]
si avoir >= 0 alors
tab_bool[i] = 1
si (fonction recursive avec i+1) retour vrai
sinon
tab_bool[i] = 0
avoir = avoir + tab_prix[i]
si (fonction recursive avec i+1) retour vrai
sinon retour faux

Attention.
Prenons les données suivantes :
3 avoirs : 500 600 et 700
6 articles : 200 250 300 300 350 et 400
Si tu prends le premier avoir, et la première combinaison d'articles, et que tu continues en retirant ces articles, tu peux avoir de la chance, mais pas forcément.
Par exemple, si tu prends 200+400=600, alors tu ne pourras plus faire aucune combinaison.
Alors que si tu commences par 250+350=600, tu pourras ensuite faire 200+300=500, et 300+400=700.

Tu dois donc gérer des scénarios :
1. Si je prends le couple 200+400=600, alors quels sont les autres combinaisons d'articles que je peux faire
2. Et si je ne prends pas le couple 200+400=600, quels sont les autres combinaisons d'articles que je peux faire.

Recher sur Google "Making change"... C'est quasiment un copier-coller du problème de "rendre la monnaie exacte" avec le minimum de pièces! ;) Tu n'as vraiment pas à trouver toutes les combinaisons possible : ton algorithme devrait tenir dans 10 lignes quand tu auraus compris les similitudes! ;)

Ca me parait très différent du problème 'rendre la monnaie'.
On doit rendre la monnaie, ok, mais on doit aussi anticiper le(s) clients(s) suivant(s), pour pouvoir leur rendre la monnaie à eux aussi.

Google it! Comment rendre la monnaie avec le minimum de pièces...

Bonjour :coucou:

Je plussoie la proposition de force brutale pour un tel problème.