Help...petit probleme concret...

[pubmarc55]

Bonjour

Un petit problème concret m'est posé :
J ai émis 16 factures d'un montant total différent pour chacune auprès d'un client.
Celui-ci m'a réglé un montant ne correspondant à aucune facture.
Ce montant peut donc correspondre à 2 ou plusieurs factures.
Comment trouver facilement (ou pas?) quelles factures (montants) ont été réglées?
Idéalement sur openoffice...
Merci et cordialement

[Sake]

Salut,

Le sujet est un peu mal posé mais je pense comprendre l'enjeu :

Le montant réglé est nécessairement la somme des montants figurant sur au moins deux factures différentes. On se demande lesquelles.

Ce n'est pas un problème qui peut avoir une solution unique. Par exemple, imaginons que tu aies émis 5 factures. Les montants de ces factures sont les suivants : M1, M2, M3, M4, M5.

Le client a réglé M1 + M2 (sans t'avoir dit à quelles factures correspond ce montant), mais par un malheureux hasard, la quantité M1 + M2 est égale à la quantité M3 + M4 + M5. Tu fais comment désormais ?

[pubmarc55]

Ce ne serait vraiment pas de chance....
car j'ai bien précisé que chaque montant est différent, j'ai bien 16 montants différents pour un seul total payé!
effectivement, il se peut que le client ait payé 2, 3, voire "x" factures....
existe t-il un raisonnement me permettant de retrouver les montants utilisés pour arriver au total payé ?
merci

[mathelot]

Les congruences peuvent être un outil pour diminuer les recherches.

si 314+271=585 alors on obtient une égalité entre les résidus modulo 2,3,5.. etc

[Robot]

Ce ne serait vraiment pas de chance....
car j'ai bien précisé que chaque montant est différent, j'ai bien 16 montants différents pour un seul total payé!
effectivement, il se peut que le client ait payé 2, 3, voire "x" factures....
existe t-il un raisonnement me permettant de retrouver les montants utilisés pour arriver au total payé ?
merci

Le fait que les montants soient tous différents ne change rien à la difficulté signalée par Sake. Un petit exemple concret : Supposons quatre factures de montants 20, 30, 40, 50 € (tous différents, n'est-ce pas). Arrive un règlement de 70 €. Quelles factures ont été réglées ?
Pour avoir une solution unique, il faut supposer que toutes les sommes d'une partie des factures sont différentes.
Du point de vue algorithmique, c'est le "problème de la somme de sous-ensembles". C'est un problème "difficile" du point de vue de la complexité (NP-complet si je ne m'abuse, je parle du problème de décision qui consiste à savoir si étant donné un ensemble d'entiers A et un entier S, il existe une partie de A dont la somme est S).
Tu peux googler "subset sum problem".

[Ben314]

Après, pour compléter ce que dit Robot, dans le cas de 16 factures, il y a 2^16=65536 "sommes de factures" que l'on peut former (pas forcément toutes différentes : voir l'exemple de Robot)

Ce nombre 65536 est "assez petit" au sens informatique, c'est à dire que, pour un ordinateur ce n'est pas très long de calculer toutes les sommes possibles pour y rechercher une somme particulière.
Par contre, je ne sais pas si c'est encore faisable avec uniquement un tableur qu'on utilise en mode "basique" (peut on faire une feuille de calcul avec 65536 lignes ?), mais on peut faire une "routine externe" au tableur qu'on utilise dans le tableur, voire peut-être avec la fonction "solveur" existant dans les tableurs récents (là, contrairement à la "routine externe", je ne suis pas du tout sûr de mon coup...)
Mais de toute façon, il faut bien comprendre que, si tu met en place une telle solution "empirique", ça ne marchera qu'avec un nombre de facture de départ "petit" (un peu au pif, je dirais de l'ordre d'une vingtaine de factures au maximum) et que si tu veut une méthode qui marche pour des nombres un peu plus grand, il va falloir faire dans le "pas mal compliqué"...

Si j'ai un peu de temps, je regarderais si la fonction "solveur" (que je ne connais presque pas) de Open Office peut répondre au problème (à moins évidement qu'un autre intervenant n'ai la réponse...)

[Pseuda]

C'est un problème classique de rapprochement des factures avec les règlements. La plupart des logiciels de comptabilité font cela.

De mémoire, si tu veux écrire un algorithme qui le fait, tu peux faire l'exhaustivité des solutions (comme le propose Robot), ou bien faire plus finement :
- commencer par éliminer bien évidemment les factures qui dépassent le montant du règlement,
- prendre parmi les montants restants, le montant le plus grand,
- calculer le reste à trouver,
- éliminer les montants trop grands,
etc...
- si on a trouvé une solution, s'arrêter (mais on peut aussi continuer pour avoir l'exhaustivité), sinon :
- remonter en choisissant le 2ème montant le plus grand,
etc...

[chan79]

Bonjour

Un petit problème concret m'est posé :
J ai émis 16 factures d'un montant total différent pour chacune auprès d'un client.
Celui-ci m'a réglé un montant ne correspondant à aucune facture.
Ce montant peut donc correspondre à 2 ou plusieurs factures.
Comment trouver facilement (ou pas?) quelles factures (montants) ont été réglées?
Idéalement sur openoffice...
Merci et cordialement

salut
avec Excel
tu mets tes montants de factures sur la première ligne de A1 à P1
En A3 tu mets la formule =A1*A2
ça donne évidemment 0 en A3
tu tires A3 vers la droite jusqu'en P3
En Q3, tu ajoutes A3+B3+...+P3
tu utilises le solveur
les cellules variables vont de $A$2 à $P$2
Objectif à définir: il faut que $Q$3 donne le montant de la somme payée par le client (qui n'est pas foutu de préciser à quelles factures elle correspond !)
Il faut mettre des contraintes (entiers égaux à 0 ou 1 pour les variables)
Enfin, cliquer sur "Résoudre"

[Mr Hall]

En supposant que chaque facture a un montant différent à toute autre facture, et que la somme payée par le client soit la somme d'au moins deux montants (d'au moins deux factures), alors le nombre de montants possibles (quand il s'agit de somme d'au moins deux factures) est la somme de n=2 à n=15 de 16!((16-n)!*n!) = 65518 façons d'additionner les factures. Avec un tableur ou un logiciel, c'est possible de résoudre ; mais directement à la main c'est difficile.