Discussion :

[Papy Octet]

Bonjour,

J’ai une série de nombres contenus chacun dans une cellule dans LibreOffice Calc. Les cellules sont contiguës (horizontalement ou verticalement).
J’ai une somme maxi dans une autre cellule que je ne peux absolument pas dépasser mais que je dois approcher au plus près.

Existe-t-il un moyen de trouver facilement quels nombres je dois additionner pour m’approcher au plus (ou d’égaler) de la somme maxi ?

Exemple :
j’ai les nombres : 1 5.42 0.15 25.8 11.56 2.23
La somme maxi est 19,35
Je dois additionner 5.42 + 11.56 + 2.23 = 19.21
Il faudra donc que je visualise dans le tableau l’emplacement des nombres sélectionnés dans l’addition optimale.

En réalité, j’ai une cinquantaine de nombres parmi lesquels je dois repérer ceux dont la somme me permettra d’approcher la valeur maxi imposée.

Comment pourrais-je me sortir de ce problème ? Quel algo utiliser ?

Merci.

[romain67480]

Salut, je pense que le plus facile, est que tu mettent tes 50 chiffres sur la même colonne et que dans une seconde tu fasses un cumulé.
ex: tu mets x chiffre colonne a 5 10 6 8 3 2
tu mets donc dans b2 = 5+10 b3 serra égale a la somme précédente + 6 et ainsi de suite, dès que tu t'approche de ta somme maximal tu sauras que le reste est a négocier

[picodev]

Bonjour,
Ton problème est plus communément connu sous le nom du problème du sac à dos ou knapsack. C'est un problème difficile en général. Commence par regarder la page wiki → https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos.

[Flodelarab]

Bonjour

Peux-tu utiliser un nombre deux fois ?

[wiwaxia]

Bonsoir,

... Ton problème est plus communément connu sous le nom du problème du sac à dos ou knapsack. C'est un problème difficile en général ...

Je n'avais pas reconnu le type de problème, mais m'étais rendu compte du nombre énorme de sommes qu'il fallait calculer, de l'ordre de 2^N (soit 2⁵⁰ ~ 10¹⁵). Piètre consolation, bien sûr.

Mais une autre idée m'était venue, je reprends donc ce que j'avais dans un premier temps renoncé à poster.

# Un tri préalable permet déjà de mieux cerner le problème:
a) Eliminer les nombres supérieurs à S_max (ici 25.8), qui ne peuvent intervenir dans la somme;
b) Classer les (N) termes restants selon l'ordre décroissant pour obtenir une liste, soit dans le cas présent: L = (11.56 , 5.42 , 2.23 , 1.00 , 0.15).

Exemple : j’ai les nombres : 1 5.42 0.15 25.8 11.56 2.23
La somme maxi est 19,35

On pourrait à ce stade songer (rêve malheureusement irréalisable !) à inventorier toutes les sommes d'au plus (N) termes pris dans l'ordre strictement croissant des indices, donc vérifiant:
S = t(n₁) + t(n₂) + ... + t(n_m) , avec 0 < n₁ < n₂ < ... < n_m <= N et 0 < m <= N ,
et en ne retenant en cours de calcul que les résultats vérifiant: S_k > S_k-1 et S_k < S_max .
Le calcul préalable des sommes rétrocumulées jusqu'au rang (r) permet d'éliminer les combinaisons conduisant à des sommes trop faibles - en cours de calcul seulement, parce que ce n'est pas un critère absolu; on trouve ainsi, en reprenant l'exemple précédent:
r = 1 : S_lim = 20.36
r = 2 : S_lim = 08.80 (*): à éliminer si l'on trouve auparavant une somme plus élevée, mais inférieure à S_max = 19.35 - ce qui est le cas ici puisque t[1] = 11.56
r = 3 : S_lim = 03.38 (**)
r = 4 : S_lim = 01.15 (**)
r = 5 : S_lim = 00.15 (**): à éliminer d'office puisque S_lim(r=2) = 8.80 .

# Ce que l'on peut envisager, c'est une séquence très longue (pour autant que la patience du programmeur et le réglage de sa machine le permette) de (N) tirages aléatoires, à valeurs non-nulles mutuellement toutes différentes, effectués sur la liste de dimension double augmentée de (N) zéros :
L' = (11.56 , 5.42 , 2.23 , 1.00 , 0.15, 0 , 0 , 0 , 0 , 0) .

La somme maximale (ici S_tab = 20.36), serait approximativement 10 fois plus élevée dans le cas de 50 termes (~ 100 à 200), et conduirait à une probabilité faible, mais non dérisoire (1), de trouver un résultat conforme à la condition: S < S_max = 19,35 ;
rien n'interdit d'ailleurs de construire progressivement un histogramme sommaire, au fur et à mesure de l'apparition des tirages successifs (2).

On mémorisera la k^ième somme obtenue, et la liste correspondante des indices, sur vérification des critères:
S_k-1 < S_k < S_max .

Et si tous les termes de la liste sont des réels à deux décimales, cela revient à manipuler des entiers 100 fois plus grands. Il ne sera pas alors improbable de trouver deux sommes égales.

(1) affirmation peut-être hasardeuse ... la distribution est représentée par une courbe en cloche; d'où l'intérêt de l'histogramme.
(2) ... ni d'envisager un procédé autre qu'un tirage de probabilité uniforme; on pourrait corriger la somme aléatoire obtenue, à l'aide des termes de la liste, afin de se rapprocher du seuil critique S_max = 19,35 , ou plus simplement arrêter le tirage dès le franchissement du seuil.

[dourouc05]

Si tu es dans Excel, tu peux tenter une formulation du sac à dos en MIP (https://fr.wikipedia.org/wiki/Probl%...h.C3.A9matique) et la résoudre avec le solveur (http://www.excel-easy.com/vba/exampl...k-problem.html). Sinon, un algorithme glouton devrait assez bien fonctionner, tant que tu ne cherches pas absolument la meilleure somme d'objets (https://fr.wikipedia.org/wiki/Probl%...rithme_glouton) ; maintenant, je ne suis pas sûr qu'il soit si facile à implémenter dans Excel sans VBA.

[Papy Octet]

Peux-tu utiliser un nombre deux fois ?

Non. Chaque nombre ne peut être utilisé qu'une seule fois.

Si tu es dans Excel, tu peux tenter une formulation du sac à dos en MIP (https://fr.wikipedia.org/wiki/Probl%...h.C3.A9matique) et la résoudre avec le solveur (http://www.excel-easy.com/vba/exampl...k-problem.html). Sinon, un algorithme glouton devrait assez bien fonctionner, tant que tu ne cherches pas absolument la meilleure somme d'objets (https://fr.wikipedia.org/wiki/Probl%...rithme_glouton) ; maintenant, je ne suis pas sûr qu'il soit si facile à implémenter dans Excel sans VBA.

Bonjour,

Je ne suis plus sous Windows depuis plus de 15 ans Je travaille avec Debian. Les goûts et les couleurs ... et surtout je suis retraité et donc n'ai plus les contraintes de mon employeur
Je peux créer un tel programme en C, Python ou Basic et ne dois pas nécessairement utiliser un tableur (LibreOffice Calc).

Merci pour les liens très intéressants donnés. Je me plonge dans cette littérature pour résoudre mon petit problème.
Pour expliquer le pourquoi de ma demande : nous sommes une toute petite association qui reçoit quelques petits subsides. La somme allouée est définie par avance et nous achats (couverts ultérieurement par le subside) ne doivent absolument pas dépasser la somme du subside. Et donc, pour "empocher" un max, il faut que nous rentrions une série de tickets de caisse dont la somme sera la plus proche de la valeur du subside.
Avec 10 tickets de caisse, le calcul manuel ... ça va mais avec 2 ou 3 dizaines de tickets, cela devient "hard" d'où ma demande.

Merci à vous pour ces suggestions.

Salut, je pense que le plus facile, est que tu mettent tes 50 chiffres sur la même colonne et que dans une seconde tu fasses un cumulé.
ex: tu mets x chiffre colonne a 5 10 6 8 3 2
tu mets donc dans b2 = 5+10 b3 serra égale a la somme précédente + 6 et ainsi de suite, dès que tu t'approche de ta somme maximal tu sauras que le reste est a négocier

Bonjour,

Merci pour cette proposition de solution qui semble être utilisable avec peu de nombres. Elle pourrait me convenir dans certains cas.

A+

[dourouc05]

Je ne suis plus sous Windows depuis plus de 15 ans Je travaille avec Debian. Les goûts et les couleurs ... et surtout je suis retraité et donc n'ai plus les contraintes de mon employeur
Je peux créer un tel programme en C, Python ou Basic et ne dois pas nécessairement utiliser un tableur (LibreOffice Calc).

Désolé de te décevoir, un module similaire existe pour LibreOffice ! (https://help.libreoffice.org/Calc/Solver) Sinon, tu peux aller voir du côté de Python avec Pyomo http://www.pyomo.org/ pour écrire le problème d'optimisation (ils fournissent un exemple, d'ailleurs : https://projects.coin-or.org/Coopr/b...215&order=name), avec des solveurs comme CBC ou GLPK pour résoudre les problèmes (les deux sont gratuits et libres : https://software.sandia.gov/download...e.html#Solvers). (Mon choix personnel se porterait plus vers Julia et JuMP pour remplacer, respectivement, Python et Pyomo, mais c'est un peu plus difficile d'accès si tu connais déjà bien Python : http://julialang.org/ et http://www.juliaopt.org/.)

Maintenant, si tu préfères bien comprendre tout ce que tu fais, je peux comprendre que ce paradigme soit difficile d'accès .

[Flodelarab]

Non. Chaque nombre ne peut être utilisé qu'une seule fois.

C'est bien ce qui me semblait. Donc, ce n'est pas un problème du sac à dos, dans lequel les quantités disponibles sont infinies.

Je peux créer un tel programme en C, Python ou Basic et ne dois pas nécessairement utiliser un tableur (LibreOffice Calc).

A ta place, je fais un programme en c en faisant toutes les possibilités avec les grosses valeurs, puis en intégrant une valeur plus petite au fur et à mesure.

Après, c'est une question de temps.

PS: on peut faire un cas spécial "tout pile" en étudiant les centièmes..., les dixièmes... les unités...

[dourouc05]

C'est bien ce qui me semblait. Donc, ce n'est pas un problème du sac à dos, dans lequel les quantités disponibles sont infinies.

Tu joues sur les mots et/ou sur les définitions : dans la version formelle du problème sur Wikipédia, on parle bien d'éléments disponibles en quantité limitée (une fois, pour être exact). https://fr.wikipedia.org/wiki/Probl%...h.C3.A9matique Le cas d'objets disponibles en quantité infinies est traité uniquement en variante (https://fr.wikipedia.org/wiki/Probl%..._enti.C3.A8res). Au contraire, l'article anglais fait plus régulièrement la distinction binaire/entier https://en.wikipedia.org/wiki/Knapsack_problem. La définition exacte du problème du sac à dos est loin d'être unique…

[Papy Octet]

Ouh-là ! J'étais bien loin d'imaginer la complexité de ce problème.

J'avais déjà eu à résoudre cela avec une dizaine de nombre et ça avait été relativement rapide à faire "à la main".
Maintenant, je me rends compte de la possible complexité du problème. Mais d'un autre côté, c'est chouette d'essayer d'apprendre des nouveautés

Je continue à suivre vos réactions diverses et instructives.

Merci.

on peut faire un cas spécial "tout pile" en étudiant les centièmes..., les dixièmes... les unités...

Le "tout pile" n'est pas obligatoire vu que je ne peux utiliser que les nombres qui me sont donnés (les tickets de caisse en occurrence).
Je vais essayer en C.
Pour ce gros problème, j'ai un peu de temps (1 bon mois) avant de devoir rendre ma liste d'achats.

Merci pour toutes vos aides précieuses.

[anapurna]

salut

regarde du cote de l'algo "subset sum" c'est une variante du sac à dos

[Papy Octet]

Bonjour,

Un tout grand MERCI pour toutes vos suggestions que j'ai commencé à étudier.

Dans le cadre d'une recherche similaire avec quelques nombres seulement, j'ai obtenu une solution avec le solveur de LibreOffice Calc là.
Il faut se dépêcher d'aller voir, ce site va bientôt fermer ... hélas.

A+

[wiwaxia]

Bonjour,

Loin de moi l'idée de te saper le moral, ni de déprécier le tableur de LibreOffice, mais je doute que celui-ci soit en mesure de livrer une solution sur une liste de 50 termes, comme cela s'est dit sur le forum concerné:

TpF ... si le choix doit se faire parmi 50 valeurs alors nous avons 2^50 soit environ 1 125 899 906 842 620 possibilités de combinaison qu’il faut calculer puis comparer avec le seuil maxi ...
Pas sûr et pas assez expérimenté avec le solveur de notre tableur préféré, je ne vois qu’une macro pour résoudre ce type de chalenge ...

L'un des intervenants s'est entraîné sur une liste de 14 termes:

Phane ... Eh bien moi je trouve …149,99 en 44 millisecondes

ce qui laisse craindre, pour l'énoncé de départ, un délai de calcul quelque peu excessif: t = 0.044*(2^50-14) = 3.0 Gs = 96 ans
et des ennuis certains compte tenu de l'obsolescence du matériel.
Encore qu'une idée essentielle y ait été apparemment mise en oeuvre:

... La valeur cible est la différence entre la valeur absolue de la somme des chiffres pondérés et la valeur cherchée. Il faut encadrer le solveur pour que les coef soient logiques (ou binaires selon les versions de LO ) et que la somme calculée reste inférieur à la somme recherchée ...

à savoir la restriction progressive de la liste initiale, susceptible d'accélérer considérablement l'émergence d'une solution satisfaisante.
D'autres ont d'ailleurs donné sur le même site des indications pertinentes sur la marche à suivre, quoiqu'ils n'aient pas su le traduire en algorithme.

Je crois que l'itération prolongée d'un tirage aléatoire des termes, assorti de conditions suffisamment restrictives, peut conduire à une bonne solution - ce qui suit est une version plus simple de ce que j'avais proposé dans un précédent message.

1°) Constituer la liste des (N) termes rangés dans l'ordre décroissant, et complétée par un zéro:
La[0] = < 9492 , 4901 , 1820 , 1440 , 1300 , 1196 , 1190 , 1101 , 805 , 447 , 0 >
On suppose la somme limite S_max = 14300;

2°) Renouveler la suite des opérations suivantes jusqu'à l'épuisement total de la liste:
a) Tester l'intervention obligatoire du 1^er terme en calculant la somme complémentaire correspondante S' = 4901 + 1820 + ... + 447 = 14200 ; on constate ici que: S' < S_max et que par conséquent La[0][1] intervient obligatoirement, ce qui donne
Lb[1] = < 4901 , 1820 , 1440 , 1300 , 1196 , 1190 , 1101 , 805 , 447 , 0 , 0 > et la solution partielle S[1] = < 9492 > , la nouvelle somme limite S_lim[1] = 4808 , et la complémentaire S' = 9299 .
On a désormais S' > S_lim[1] , le nouveau 1^er terme ne sort plus d'office.

b) Eliminer les termes dépassant S_lim[1], et qui ne peuvent plus être inclus dans la sommation: c'est le cas de La[1][1] = 4901 , d'où la nouvelle liste:
Lb[1] = < 1820 , 1440 , 1300 , 1196 , 1190 , 1101 , 805 , 447 , 0 , 0 , 0 >

c) Procéder au tirage aléatoire de l'une des valeurs restantes, par exemple 1190, conduisant à la nouvelle liste:
Lc[1] = < 1820 , 1440 , 1300 , 1196 , 1101 , 805 , 447 , 0 , 0 , 0 , 0 > ainsi qu'à S_lim[2] = 3618 et S[2] = < 9492 , 1190 > .

La disparition de tous les termes non-nuls détermine l'arrêt de la boucle; on parvient alors à:
L[k] = < 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 > , S[n] = < 9492 , 1190 , ...> (comportant n termes non-nuls) et S_lim[n] < S_lim = 14300 .
Le premier test (a), destiné à éliminer les combinaisons de plus faible somme, peut devenir à la limite contestable, si l'on a par exemple: S'[i] = S_lim - 1 ;
il pourrait être remplacé par une condition moins stricte, par ex.:
S'[i] < S_lim[j] - t[k] , où t[k] représente le plus petit terme terme positif de la liste actuelle L[i] .

Et d'ailleurs, rien n'interdit le calcul préliminaire et systématique des sommes de 2, 3 (voire 4) termes de la liste, afin de sélectionner Max(S | S < S_max) ; on saisirait ainsi rapidement les éventuelles solutions simples.

... Je peux créer un tel programme en C, Python ou Basic ...

Cela doit se programmer sans trop de difficulté.

[Papy Octet]

Comment une "simple question" à priori peu générer autant d’excitation de neurones et de transistors

Là, je suis moi-même surpris et un peu dépassé par les événements.
Je m'étais bien rendu compte que ma question pouvait être complexe à résoudre pour avoir déjà essayé manuellement avec une dizaine de nombres. Mais de déchaîner les passions à ce point ... c'est vraiment intéressant.

Merci à vous tous pour toutes ces suggestions.
A+

[tbc92]

Un petit apport à mon tour.

1. Tu as des montants en euros/centimes. Sur un plan purement informatique, tu as tout intérêt à travailler en centimes. Additionner des entiers est plus facile qu'additionner des réels ou des décimaux.
2. Quel est l'objectif ? Plus précisément, quel est le temps de traitement maxi ? Est-ce que tu as besoin d'un traitement qui te renvoie la réponse en moins de x secondes, ou, autre option, tu veux un traitement, qui s'arrête au bout de x secondes, et qui affiche la meilleure solution trouvée jusque là... et tant pis si on pouvait légèrement améliorer le résultat obtenu ....

[Papy Octet]

Bonjour tbc92,

Traiter les montants en centimes plutôt qu'en euros, centimes : je n'y avais pas pensé et ... je ne suis pas le seul

Dans ce cas-ci, je n'ai pas trop de contrainte de temps. Mais bien entendu je ne dois pas attendre 1 mois

Notre ami Phane propose une solution avec le solveur de LibreOffice Calc dans cette discussion déjà signalée plus haut, au message #13.
Avec 50 valeurs : 30 secondes de calcul

A+

[tbc92]

En fait, une fois qu'on a vu qu'on travaillait avec des entiers, et pas avec des réels, et plus précisément des entiers pas très grands (le plus grand est 1156 dans le premier exemple), on va voir que l'algorithme va converger très vite, même avec des nombres de tickets assez élevés.

Imaginons 100 tickets, avec des montants moyens de 1000 centimes, et donc un montant total de 100 000 centimes.
Avec ces 100 tickets, on a 2^100 combinaisons possibles (c'est à dire énormément de combinaisons). Et pour toutes ces combinaisons, la somme des tickets sélectionnés donne un nombre entre 1 et 100000. Pour un montant cible donné, on a donc énormément de combinaisons qui vont donner le montant visé. Et donc l'algorithme a de grandes chances de trouver très vite une solution parfaite. Statistiquement, il suffit d'en analyser 100 000, puisqu'il n'y a que 100 000 sommes possibles.

Alors que, autre configuration, on a 50 tickets, mais avec un montant moyen de 10 000 centimes. Dans ce cas, la somme des 50 tickets est de 500 000 centimes.
Dans cette nouvelle configuration, le temps moyen de traitement va être 5 fois plus élevé que dans le cas précédent, alors qu'on a réduit le nombre de tickets de 100 à 50.

J'ai fait l'expérience avec un algorithme que je viens d'écrire, et ces évaluations sont confirmées... au-delà même de ce que j'imaginais.
15 centièmes de secondes en moyenne pour 100 tickets, avec un montant moyen de 5 000 centimes par ticket.
10 secondes en moyenne pour 100 tickets , avec un montant moyen de 50 000 centimes par ticket.
L'explication est certainement que les tests que j'ai faits étaient tous sur des ticket de l'ordre de 5000 centimes, et j'ai fait mes améliorations dans cette configuration.

[dourouc05]

Code écrit en cinq minutes (en Julia : knapsack.txt en pièce jointe), ça me donne des solutions endéans la seconde pour cinquante montants (exemple repris du fichier ODS). Bon, comme solveur, derrière, j'utilise Gurobi, qui est commercial, cher (sauf pour les académiques ) et très bon ; on doit avoir des résultats similaires avec SCIP (http://scip.zib.de/), à condition d'exporter le modèle sous la forme d'un fichier LP (facile à générer autrement que par mon script, voir exemple en pièce jointe) et de le passer en argument à SCIP.

À mon avis, dire que tu as une bonne solution parce qu'elle s'exécute en trente secondes sur tes cinquante tickets, ce n'est pas très satisfaisant d'un point de vue intellectuel, il y a moyen de faire bien mieux ! La solution de tbc92 me paraît bien meilleure que les résultats obtenus sur l'autre forum.

[Papy Octet]

...
À mon avis, dire que tu as une bonne solution parce qu'elle s'exécute en trente secondes sur tes cinquante tickets, ce n'est pas très satisfaisant d'un point de vue intellectuel, il y a moyen de faire bien mieux ! La solution de tbc92 me paraît bien meilleure que les résultats obtenus sur l'autre forum.

En effet, d'un point de vue purement académique, tu as raison et on devrait chercher à optimiser au mieux si le besoin était "commercial" et/ou "professionnel". mais là, comme tu le soulignes, il existe des logiciels très performants.
Mes besoins sont bien plus modeste. Ils se limitent à la gestion d'une petite association et "attendre" 30 secondes après la réponse n'est vraiment pas rédhibitoire pour moi

Merci toute fois pour ces infos qui pourront certainement en intéresser plus d'un.

A+