Discussion :

[florianjin]

Bonjour,
Je cherche une formule mathématique pour un projet.

J'ai un un chiffre du style 14
Et je cherche a savoir combien de 5, de 4 et de 2 je peux caser.
La réponse que je cherche pour le chiffre 14 c'est deux 5 et un 4.


l'objectif étant de toujours caser les plus gros chiffres.

dit différemment,
J'ai des sacs de 2 pommes
des sacs de 4 pommes
des sacs de 5 pommes


l'objectif c'est que si la personne prend 14 pommes, faire en sorte de donner le moins de sac possible
Il serait con de donner au client 7 sacs de pommes alors que 3 suffisent.

j'ai la solution qui consiste a faire plein de calcul a la suite
Exemple pour 14
14-5=9
9-5=4
4-5=erreur
4-4=0
fin du calcul

mais c'est beaucoup trop long
car évidement l'idée ce n'est pas d'avoir l'information sur un chiffre, mais sur 200 voir plus avec des chiffres 2,4,5 qui changent en fonction des besoins.

[WhiteCrow]

Bonjour,
c'est le problème du rendu de monnaie.
L'algorithme que tu décris étant l'algorithme glouton naïf. Il ne donne pas forcément une solution optimale suivant les bases. Le contre exemple classique étant dans le cas de la base {1,3,4}, l'algo glouton donne 6=4+1+1 alors que la solution optimale est 6=3+3.

C'est un ensemble de problèmes très intéressants sur lesquels tu trouveras beaucoup de littérature en cherchant un tout petit peu.

[dourouc05]

mais c'est beaucoup trop long

Je ne suis pas sûr que tu auras un bien meilleur algorithme en termes de complexité, pourtant, sans sortir des algorithmes plus ésotériques. Pour un rendu de X et n pièces disponibles, tu fais O(X n) opérations, le pire cas étant celui où tu n'utilises que la pièce la plus petite (dont la "pire" valeur est 1). L'algorithme dynamique, toujours optimal lui, aura la même complexité en temps dans le pire cas (mais une moins bonne complexité en espace). Je n'ai pas vu dans la littérature d'algorithme qui ne dépende pas de la valeur à convertir…

Ton but est-il d'avoir une solution assez efficace en pratique ou c'est plus une étude théorique ? Dans le premier cas, les nombres que tu peux utiliser sont-ils fixes et sont-ils canoniques (dans le sens où l'algorithme glouton sera optimal) ? L'algorithme glouton est-il vraiment trop lent en pratique ou bien estimes-tu qu'il le sera ?

[florianjin]

:glouton est-il vraiment trop lent en pratique ou bien estimes-tu qu'il le sera ?

L'utilisation c'est pour un site internet, donc le nombre de fois ou traitement sera fait dépendra du nombre de produit, d'un stock, et du conditionnement possible, qui peut changer à tout moment.
Donc l'objectif de base, serait que si un stock est a 100, il me faudrait les 100possibilités qui s'affichent.

Plus la formule est compliqué, plus il faut de temps pour que la page s'ouvre.
Donc je cherche toujours la solution la plus optimisé.



Ma référence quand je cherche une solution,
c'est comme pour les différents algo pour faire un tri, différente méthode qui ont une différence fulgurante.
Prendre la mauvaise méthode serait suicidaire à l'utilisation.

On m'a proposé sur une autre page, il faut que je l'adapte, mais cela semble déjà plus opti.

$value=28;
echo "nombre de fois 5 : ". $five=intval($value / 5). PHP_EOL;
echo "nombre de fois 4 : ". $four=intval(($value % 5) / 4). PHP_EOL;
echo "nombre de fois 2 : ". $two=intval(($value - ($five * 5)- ($four * 4)) / 2). PHP_EOL ;

[Flodelarab]

Bonjour

On peut quand même noter que dans l'exemple :

• Il n'y aura jamais plus d'un sac de 2, car 2 sacs de 2 peuvent être remplacés avantageusement par un sac de 4.
• Il n'y aura jamais plus que 4 sacs de 4, car 5 sacs de 4 peuvent être remplacés avantageusement par 4 sacs de 5.

Donc 0 ou 1 sac de 2, et 0 à 4 sacs de 4, cela fait 10 possibilités seulement. Le reste en sacs de 5.
0 2 4 6 8 10 12 14 16 18

On peut noter aussi que l'imparité ne peut venir que du nombre impair de sacs de 5. Pour atteindre 213, on testera 1, 3, 5, etc mais pas 2, 4, 6, etc.
Le plus grand inférieur est 41*5=205 (43*5=215). Donc 213=41*5+2*4

[mathieu]

On m'a proposé sur une autre page, il faut que je l'adapte, mais cela semble déjà plus opti.

avez-vous vu le message de WhiteCrow ?
cet algorithme n'est pas du tout optimisé si vous n'avez pas un système canonique.

Plus la formule est compliqué, plus il faut de temps pour que la page s'ouvre.

ce n'est pas ce genre de calcul qui prennent le plus de temps. donc faites des essais, c'est tout à fait possible que des calculs de combinaisons de 1 000 produits se fassent assez rapidement pour ne pas être gênant pour l'utilisateur.
d'habitude pour les sites sur lesquels je travaille, je fixe une durée de 1 seconde maximum pour la génération complète d'une page.

[florianjin]

avez-vous vu le message de WhiteCrow ?
d'habitude pour les sites sur lesquels je travaille, je fixe une durée de 1 seconde maximum pour la génération complète d'une page.

la page ne faisant pas que ce calcul, pour arriver a une seconde, il faut quoi qu'il arrive optimiser à 100% chaque calcul.
Si je gagne 0,1s en trouvant la bonne formule, je peux rajouter un autre calcul de 0,1s

Le méthode glouton de base est trop lourde pour mon utilisation, c'est un fait, après l'information étant utile puisqu'il donne un nom a ce que je dois chercher. (ou donner un nom a ce que l'on cherche, permet de faire de meilleur recherche)


Le site que je fais est rempli de calcul pour réduire les erreurs pendant les préparations, et la perte d'argent en conditionnement.

Dans le cas présent mon cerveau me dit qu'il y a forcément une méthode plus rapide, mais j'ai un blocage que je n'arrive pas expliquer, d'où la demande.
Pas mal de réponse m'ont déjà pas mal débloqué.

Bonjour

On peut quand même noter que dans l'exemple :

• Il n'y aura jamais plus d'un sac de 2, car 2 sacs de 2 peuvent être remplacés avantageusement par un sac de 4.
• Il n'y aura jamais plus que 4 sacs de 4, car 5 sacs de 4 peuvent être remplacés avantageusement par 4 sacs de 5.

Donc 0 ou 1 sac de 2, et 0 à 4 sacs de 4, cela fait 10 possibilités seulement. Le reste en sacs de 5.
0 2 4 6 8 10 12 14 16 18

On peut noter aussi que l'imparité ne peut venir que du nombre impair de sacs de 5. Pour atteindre 213, on testera 1, 3, 5, etc mais pas 2, 4, 6, etc.
Le plus grand inférieur est 41*5=205 (43*5=215). Donc 213=41*5+2*4

Merci pour l'explication, cela me donne des idées pour revoir le fonctionnement.
Je vais tester les différentes méthode, voir ce qui fonctionne dans 100% des cas.

[mathieu]

j'ai mis en pièce jointe un algorithme qui teste la différence entre un algorithme qui cherche la meilleure répartition et un algorithme glouton.

ensuite si vous avez beaucoup de calculs, il faudra aussi voir si vous pouvez mettre certains résultats en cache, cela peut aussi rendre l'affichage des pages web plus rapide.

[florianjin]

j'ai mis en pièce jointe un algorithme qui teste la différence entre un algorithme qui cherche la meilleure répartition et un algorithme glouton.

ensuite si vous avez beaucoup de calculs, il faudra aussi voir si vous pouvez mettre certains résultats en cache, cela peut aussi rendre l'affichage des pages web plus rapide.

J'ai effectivement prévu de faire un calcul du temps entre les différents choix.
Précision le code fournis donne un résultat faux.
Si on prend la valeur 22 et 7,4,2 il va informer 3X7

Pour la mise en cache, c'est aussi prévu, mais cela reste limité, vu que des modifications risque d'être faite.

[mathieu]

Si on prend la valeur 22 et 7,4,2

dans la liste des paquets, vous devez obligatoirement ajouter 1 sinon ça voudrait dire que vous ne faites pas de livraison si le client commande 22 produits (c'est peut-être ce que vous souhaitez ?).

[florianjin]

dans la liste des paquets, vous devez obligatoirement ajouter 1 sinon ça voudrait dire que vous ne faites pas de livraison si le client commande 22 produits (c'est peut-être ce que vous souhaitez ?).

certain produit ne sont pas possible d'être commandé en une unité.

Pour 22, dans l'exemple, ce qui est recherché c'est 2X7 + 2X4
le 7,4,2 peut devenir 8,3,2, ou 6,2,1 ou encore 10,7,3,2