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

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