IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Inscrit en
    Février 2004
    Messages
    84
    Détails du profil
    Informations forums :
    Inscription : Février 2004
    Messages : 84
    Points : 90
    Points
    90
    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 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Points : 7 163
    Points
    7 163
    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 régulier
    Inscrit en
    Février 2004
    Messages
    84
    Détails du profil
    Informations forums :
    Inscription : Février 2004
    Messages : 84
    Points : 90
    Points
    90
    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 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Points : 7 163
    Points
    7 163
    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
    4 038
    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 : 4 038
    Points : 9 347
    Points
    9 347
    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 régulier
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    Décembre 2014
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 56
    Localisation : Canada

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

    Informations forums :
    Inscription : Décembre 2014
    Messages : 52
    Points : 112
    Points
    112
    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
    4 038
    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 : 4 038
    Points : 9 347
    Points
    9 347
    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 régulier
    Homme Profil pro
    Analyste-programmeur
    Inscrit en
    Décembre 2014
    Messages
    52
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 56
    Localisation : Canada

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

    Informations forums :
    Inscription : Décembre 2014
    Messages : 52
    Points : 112
    Points
    112
    Par défaut
    Google it! Comment rendre la monnaie avec le minimum de pièces...

  9. #9
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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.

Discussions similaires

  1. Réponses: 1
    Dernier message: 02/03/2017, 15h00
  2. Réponses: 3
    Dernier message: 12/04/2015, 14h00
  3. Lister toutes les combinaisons d'éléments
    Par Loceka dans le forum Prolog
    Réponses: 5
    Dernier message: 15/04/2007, 01h11
  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, 21h09
  5. Lister toutes les combinaisons...
    Par monstroplante dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 04/11/2005, 22h10

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