1. #1
    Membre du Club
    Inscrit en
    février 2004
    Messages
    43
    Détails du profil
    Informations forums :
    Inscription : février 2004
    Messages : 43
    Points : 45
    Points
    45

    Par défaut 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

  2. #2
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    juin 2007
    Messages
    4 045
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 4 045
    Points : 7 186
    Points
    7 186

    Par défaut

    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.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  3. #3
    Membre du Club
    Inscrit en
    février 2004
    Messages
    43
    Détails du profil
    Informations forums :
    Inscription : février 2004
    Messages : 43
    Points : 45
    Points
    45

    Par défaut

    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

  4. #4
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    juin 2007
    Messages
    4 045
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 4 045
    Points : 7 186
    Points
    7 186

    Par défaut

    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
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 820
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 820
    Points : 3 804
    Points
    3 804

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Membre du Club
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    décembre 2014
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France

    Informations professionnelles :
    Activité : Analyste-programmeur
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2014
    Messages : 29
    Points : 59
    Points
    59

    Par défaut

    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!

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 820
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 820
    Points : 3 804
    Points
    3 804

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Membre du Club
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    décembre 2014
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France

    Informations professionnelles :
    Activité : Analyste-programmeur
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2014
    Messages : 29
    Points : 59
    Points
    59

    Par défaut

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

  9. #9
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 974
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 974
    Points : 6 971
    Points
    6 971

    Par défaut

    Bonjour

    Je plussoie la proposition de force brutale pour un tel problème.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

Discussions similaires

  1. Réponses: 1
    Dernier message: 02/03/2017, 14h00
  2. Réponses: 3
    Dernier message: 12/04/2015, 13h00
  3. Lister toutes les combinaisons d'éléments
    Par Loceka dans le forum Prolog
    Réponses: 5
    Dernier message: 15/04/2007, 00h11
  4. retouver toute les combinaison
    Par sami_c dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 22/03/2006, 20h09
  5. Lister toutes les combinaisons...
    Par monstroplante dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 04/11/2005, 21h10

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo