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 :

Meilleure combinaison possible


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éprouvé
    Avatar de HULK
    Inscrit en
    Juillet 2003
    Messages
    1 276
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Juillet 2003
    Messages : 1 276
    Points : 1 281
    Points
    1 281
    Par défaut Meilleure combinaison possible
    Bonjour,

    le tableau suivant est trié par date d'expiration dans l'ordre croissant
    je voudrais trouver la combinaison de number dont la somme des quantités correspondantes serait égale à la quantité que je dois trouver en priorisant les dates d'expiration les plus proche

    exemple :
    je veux une quantité de 3700, l'algo doit me trouver 1 / 2 / 5
    je veux une quantité de 2500, l'algo doit me trouver 1 / 3

    Nom : Capture.JPG
Affichages : 193
Taille : 18,4 Ko

    je sais qu'il y a 6 * 5 * 4 * 3 * 2 possibilités.
    Est ce quelqu'un aurait une idée de à quoi pourrait ressembler l'algorithme?

    Merci.
    j'suis vert !

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 643
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 643
    Points : 188 653
    Points
    188 653
    Par défaut


    Ca ressemble vachement au subset-sum problem : trouver un sous-ensemble d'items dont la somme vaut une constante. Il existe une myriade d'algorithmes pour ça (https://fr.wikipedia.org/wiki/Probl%...sous-ensembles).

    Les algos classiques vont ignorer ton objectif de date d'expiration. Je formaliserais ça comme un problème de sac à dos (https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos) : les capacités sont les quantités, la capacité du sac la quantité que tu veux trouver, les valeurs dépendraient de la date d'expiration (très grande valeur pour une date prochaine, petite sinon, à toi de voir quelle fonction correspond le mieux à ton besoin). Pour l'algorithme, tente la programmation dynamique, algorithme le plus classique pour ce problème (si ça ne marche pas assez vite, on peut toujours trouver autre chose) --- par exemple, https://github.com/google/or-tools/b...psack_solver.h est une interface pour une série d'algorithmes qui fonctionnent chacun très bien dans une catégorie d'instances.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 299
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 299
    Points : 12 782
    Points
    12 782
    Par défaut
    Pour moi, de ce que je comprends, il suffit de trouver la PREMIERE bonne somme de quantité en parcourant la colonne quantity dans l'ordre donné par le tri selon la date d'expiration.
    Cordialement.

  4. #4
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 394
    Points : 4 363
    Points
    4 363
    Par défaut
    Bonjour,

    Je crois que je ferais d'abord un tri (un tri d'index si on ne veut pas modifier la table d'origine) par ordre de quantité décroissante.

    Pour aussi peu d'éléments cela n'a pas beaucoup d'intérêt mais cela pourrait le devenir si le nombre N est important

    Si on est sur un indice[n] et que la somme en cours, somme[n] + val[m > indice[n]], est supérieure à la cible on augmente j = indice[n] jusqu'à ce que val[j] <> val[indice[n]] alors indice[n] = j et on reprend l'étape suivante à m=indice[n]+1. On peut avoir besoin de 2 tableaux (indices et sommes) de N positions.

    Sauf erreur, on devrait avoir au maximum 2N-1 cas différents (un peu moins avec les valeurs répétées).

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  5. #5
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 299
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 299
    Points : 12 782
    Points
    12 782
    Par défaut
    Si on tri par date, on a pas besoin de se faire tous les cas, on prend le premier qui correspond

    Ou mieux par date puis quantity
    Cordialement.

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 085
    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 085
    Points : 9 457
    Points
    9 457
    Par défaut
    Si les données sont :
    A 2000 1er Janvier
    B 1000 2 Janvier
    C 1500 3 Janvier
    D 500 9 Janvier
    et si la somme à trouver est 2500, on veut avoir A+D ou B+C ?

    Et sur les exemples suivants, on veut quoi (toujours pour un total de 2500) ?
    A 500 1er Janvier
    B 1000 2 Janvier
    C 1500 3 Janvier
    D 2000 9 Janvier

    A 500 1er Janvier
    B 1000 2 Janvier
    C 800 3 Janvier
    D 1500 4 Janvier
    E 1200 5 Janvier
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 394
    Points : 4 363
    Points
    4 363
    Par défaut
    Bonjour disedorgue,

    Citation Envoyé par disedorgue Voir le message
    Si on tri par date, on a pas besoin de se faire tous les cas, on prend le premier qui correspond...
    Dans tous les cas on s'arrête à la première solution. Si les données sont triées par quantité on évite de tester trop de cas si il y a des répétitions de valeurs (voir l'esquisse d'algo que j'ai proposé).

    Comme le suggère tbc92 la priorisation des dates ne jouera que pour la première date de la solution qui sera la plus ancienne, mais l'âge moyen de cette solution peut s'avérer bien inférieure à une autre dont la première date serait pourtant plus récente.

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  8. #8
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 299
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 299
    Points : 12 782
    Points
    12 782
    Par défaut
    si on tri les quantity, le cas de 3700 ne sera pas le bon puisque le premier que l'on trouvera sera 3000 et 700
    Cordialement.

  9. #9
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 394
    Points : 4 363
    Points
    4 363
    Par défaut
    Bonjour,

    Cela pose bien un pb de définition car 3000 et 700 sont des dates plus proches (0 j) que 2000, 1000 et 700 (1 j + 2 j).

    Par ailleurs, il n'y a pas 6! cas mais ici plutôt de l'ordre de 26/2 - 1 soit 31 (la division par 2 à cause des 2x500 et -1 car une solution sans aucune date ne peut exister).

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  10. #10
    Membre éprouvé
    Avatar de HULK
    Inscrit en
    Juillet 2003
    Messages
    1 276
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Juillet 2003
    Messages : 1 276
    Points : 1 281
    Points
    1 281
    Par défaut
    Et sur les exemples suivants, on veut quoi (toujours pour un total de 2500) ?
    A 500 1er Janvier
    B 1000 2 Janvier
    C 1500 3 Janvier
    D 2000 9 Janvier

    - A + B = 1500 < 2500, on continue
    - A + B + C = 3000 > 2500, on ne valide pas
    - A + B + C + D = 3500 > 2500, on ne valide pas
    - apres c'est un peu là que je bloque, avec quelle combinaison on continue pour essayer de privilégier l'ordre croissant des dates.
    A + C + D ....
    ou alors dès le depart on test A + B puis A + C puis A + D ....
    j'suis vert !

  11. #11
    Membre éprouvé
    Avatar de HULK
    Inscrit en
    Juillet 2003
    Messages
    1 276
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Juillet 2003
    Messages : 1 276
    Points : 1 281
    Points
    1 281
    Par défaut
    Bonjour, merci pour ta réponse, j'ai entamé des recherches dans ce sens.

    Citation Envoyé par dourouc05 Voir le message
    Ca ressemble vachement au subset-sum problem : trouver un sous-ensemble d'items dont la somme vaut une constante. Il existe une myriade d'algorithmes pour ça (https://fr.wikipedia.org/wiki/Probl%...sous-ensembles).

    Les algos classiques vont ignorer ton objectif de date d'expiration. Je formaliserais ça comme un problème de sac à dos (https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos) : les capacités sont les quantités, la capacité du sac la quantité que tu veux trouver, les valeurs dépendraient de la date d'expiration (très grande valeur pour une date prochaine, petite sinon, à toi de voir quelle fonction correspond le mieux à ton besoin). Pour l'algorithme, tente la programmation dynamique, algorithme le plus classique pour ce problème (si ça ne marche pas assez vite, on peut toujours trouver autre chose) --- par exemple, https://github.com/google/or-tools/b...psack_solver.h est une interface pour une série d'algorithmes qui fonctionnent chacun très bien dans une catégorie d'instances.
    j'suis vert !

  12. #12
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 299
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 299
    Points : 12 782
    Points
    12 782
    Par défaut
    Citation Envoyé par HULK Voir le message
    Et sur les exemples suivants, on veut quoi (toujours pour un total de 2500) ?
    A 500 1er Janvier
    B 1000 2 Janvier
    C 1500 3 Janvier
    D 2000 9 Janvier

    - A + B = 1500 < 2500, on continue
    - A + B + C = 3000 > 2500, on ne valide pas
    - A + B + C + D = 3500 > 2500, on ne valide pas
    - apres c'est un peu là que je bloque, avec quelle combinaison on continue pour essayer de privilégier l'ordre croissant des dates.
    A + C + D ....
    ou alors dès le depart on test A + B puis A + C puis A + D ....
    ça dépend de ta contrainte:
    Si c'est juste la première date qui compte, dans ce cas tu dois tester A+B puis A+C puis A+D, ...

    Si toutes les dates comptent, alors A+B, puis A+B+C, ...puis A+B+..+X tant que < à la valeur recherchée, puis A+C, puis A+C+D+..+X ...
    Cordialement.

  13. #13
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 085
    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 085
    Points : 9 457
    Points
    9 457
    Par défaut
    Tu essaies de solutionner le problème (je teste A+B, ou A+C ...) mais il faut d'abord avoir une formulation précise du problème.
    Que veut le client ?
    Je veux 2500 unités et parmi les différentes combinaisons qui donnent 2500, je veux celle où la première livraison arrive le plus tôt possible. Donc 500+2000 dans l'exemple.
    Ou alors
    Je veux 2500 unités et parmi les différentes combinaisons qui donnent 2500, je veux celle où la dernière livraison arrive le plus tôt possible. Donc 1000+1500 dans l'exemple.
    Ou alors
    Je veux 2500 unités et parmi les différentes combinaisons qui donnent 2500, je veux celle où la date '''moyenne''' arrive le plus tôt possible. Donc 1000+1500 dans l'exemple.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  14. #14
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 434
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 434
    Points : 5 846
    Points
    5 846
    Par défaut
    salut

    ce n'est qu'une date de livraison ou d'expiration comme il le formule
    on peut penser que les dates les plus proches deviennent les plus urgentes

    Cordialement
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  15. #15
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 085
    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 085
    Points : 9 457
    Points
    9 457
    Par défaut
    Il y a d'autres questions qui peuvent influer sur la façon de résoudre le problème.
    - Si les données 'standard' sont du type '12456, 3401, 345, 402, 506, et un millier de nombres de ce type, et qu'on veut un total de 398703, il y a plein de nombres, mais peu de combinaisons qui vont donner le total voulu.
    - Si les données standard sont comme dans l'exemple, des nombres du type 100,300,500, 650, 1800, etc etc (un millier de nombres de ce type, à peu près tous multiples de 100) et qu'on veut un total de 165000, il y a a priori énormément de combinaisons qui vont convenir, et le critère sur les dates devra intervenir 'tôt' dans le processus de choix.
    - Si la somme des nombres donne un total à peine plus grand que le nombre visé, ou beaucoup plus grand, ça va jouer aussi.
    Et enfin, si on parle de 10 nombres, ou de 50000 nombres, dans un cas, on peut être totalement bourrin, et dans l'autre, on doit vraiment faire en sorte que l'algorithme soit très pointu.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Meilleure combinaison possible avec plusieurs choix
    Par jmmomg dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 15/01/2017, 09h54
  2. Déterminer la meilleure combinaison possible
    Par tfuhr dans le forum Macros et VBA Excel
    Réponses: 7
    Dernier message: 06/12/2012, 19h39
  3. trouver les combinaisons possibles d'un tableau ?
    Par titoumimi dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 20/09/2006, 20h29
  4. toutes les combinaisons possibles
    Par marocleverness dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 29/05/2006, 00h11
  5. Sortir d'un tableau les combinaisons possibles
    Par juelo dans le forum Algorithmes et structures de données
    Réponses: 33
    Dernier message: 26/03/2006, 17h11

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