Discussion :

[HULK]

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



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.

[dourouc05]

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.

[disedorgue]

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.

[Guesset]

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 2^N-1 cas différents (un peu moins avec les valeurs répétées).

Salutations

[disedorgue]

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

[tbc92]

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

[Guesset]

Bonjour disedorgue,

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

[disedorgue]

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

[Guesset]

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 2⁶/2 - 1 soit 31 (la division par 2 à cause des 2x500 et -1 car une solution sans aucune date ne peut exister).

Salutations

[HULK]

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 ....

[HULK]

Bonjour, merci pour ta réponse, j'ai entamé des recherches dans ce sens.

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.

[disedorgue]

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 ...

[tbc92]

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.

[anapurna]

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

[tbc92]

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.