algo optimal rendu de monnaie

Citation:

---

Envoyé par tyrtamos

Je n'avais pas vu cette configuration. Je l'ai essayée et... tu as raison! J'ai compris pourquoi, et j'ai corrigé mon algorithme.

---

Faudra penser à celui qui passe les pièces dans l'ordre croissant (ex print(tuple(rendumonnaie(((1, 2), (3, 2), (4, 1)), 6)))) car là il ne sort pas la solution 4, 1, 1 (oui, le test du couillon dans sa plus pure expression). Un petit tri au début de la fonction peut-être...

Il y a encore un petit défaut de syntaxe ici: if arendre > sum([p*n for p, n in C]). C'est if arendre > sum(p*n for p, n in C) qu'il faut écrire.
On pourrait penser que c'est équivalent (et dans le cas actuel, si on néglige la ram inutilement consommée, ça l'est) mais c'est une mauvaise habitude d'intégrer un tuple/list dans un truc qui est déjà fait pour traiter un itérable, car bien souvent ledit truc fonctionne à l'économie mais si on lui passe un tuple/list, tuple/list alors entièrement créé avant l'appel, l'économie ne se fait plus.
Exemple

Code:

---

1 2 3

def fct(n): print(n) return n == 5

---

Si on écrit print(any([fct(x) for x in range(10)])) on aura à l'écran tous les chiffres de 0 à 9 avant d'avoir le résultat True, résultat pourtant inévitable sitôt le 5 atteint. Mais si on écrit print(any(fct(x) for x in range(10))) là on voit la recherche s'arrêter au 5 ;)

Bonjour Sve@r,

Citation:

---

Envoyé par Sve@r

Faudra penser à celui qui passe les pièces dans l'ordre croissant (ex print(tuple(rendumonnaie(((1, 2), (3, 2), (4, 1)), 6)))) car là il ne sort pas la solution 4, 1, 1 (oui, le test du couillon dans sa plus pure expression). Un petit tri au début de la fonction peut-être...

---

J'ai ajouté un tri de C au début de la fonction:

Code:

---

1 2	# Etre sûr que les valeurs de la caisse sont dans le bon ordre C.sort(key=itemgetter(0), reverse=True)

---

Code:

---

Il y a encore un petit défaut de syntaxe ici: if arendre > sum([p*n for p, n in C]). C'est if arendre > sum(p*n for p, n in C) qu'il faut écrire.

---

Ce n'est pas un problème de syntaxe, mais un travail inutile. J'ai modifié!
Je connais le problème, mais j'ai toujours des réticences, parce qu'il faut vraiment se pencher sur les spécificités de Python: container, generator, iterator, iterable, etc...
Par exemple:
[p*n for p, n in C] ===> est une liste compréhension, et donc un container, qui est aussi un iterable: c'est ce que j'ai utilisé avec sum.
(p*n for p, n in C) ===> est un générateur
p*n for p, n in C ===> est aussi un générateur mais provoque une erreur de syntaxe en dehors d'une fonction comme sum qui demande un iterable.
etc...

Avec, en plus:
- un générateur est un itérateur
- un itérateur est un iterable
- un container (list, set, dic compréhension) est aussi un iterable

Il y a vraiment de quoi se perdre, et je ne suis même pas sûr d'en avoir compris toutes les subtilités... En dehors de la doc Python, quelques explications complémentaires ici:
https://nvie.com/posts/iterators-vs-generators/
https://stackoverflow.com/questions/...-and-iterators

J'ajoute ces améliorations dans le code précédent.

Merci! Je reste à l'écoute s'il y a d'autres problèmes ou d'autres améliorations!

Citation:

---

Envoyé par tyrtamos

J'arrive certainement un peu tard, mais ça fait pas mal de temps que ce problème de rendre la monnaie m'intrigue, et j'ai creusé un peu.

---

Si tu veux creuser ce sujet, il s'agit du problème du sac à dos (en anglais : knapsack problem) dont voici le lien Wikipédia français : https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos

Bonjour Pyramidev,

Merci pour le lien! Il est vrai que j'ai débarqué sur le sujet du "rendu monnaie" sans rien regarder sur ce qui avait été écrit déjà sur le sujet, et je m'aperçois que c'est un problème assez général.

En plus, j'ai déjà eu personnellement un problème à résoudre proche du "sac à dos": celui du chargement de ma 1ère caravane de vacances, dont le poids était à la limite de ce que pouvait supporter ma petite voiture d'alors (une Peugeot 104). J'avais fait la liste des objets que je pouvais emporter, évalué leur poids, tout rentré dans une base de données (sur Apple II), et j'ai dû sélectionner les objets à emporter pour ne pas dépasser la charge utile. Je n'avais pas d'algorithme informatique pour ça, mais ça a marché: j'ai fait cette année-là 3000km avec cette caravane, c'était en... 1982.

Mais ce problème, comme celui du sac à dos, est plus complexe que le rendu de monnaie, parce qu'il est multidimensionnel: en plus du poids, les objets peuvent avoir un intérêt plus ou moins grand d'être emportés (ex: la sécurité est plus importante que le confort), leur volume peut compter aussi, ainsi que la plus ou moins grande facilité à les remplacer quand on ne les a pas (on peut se passer de vaisselle si on a accès à un restaurant là où on va). Etc... Ainsi, l'optimum n'est pas ici dans le nombre minimum d'objets à emporter.

Je me rends bien compte qu'l ne peut pas y avoir d'algorithme simple et parfait pour résoudre des problèmes aussi complexes. Des recherches "à tâtons" sont inévitables mais elles ne sont pas déplaisantes à construire! :D

Salut,

Citation:

---

Envoyé par tyrtamos

Il est vrai que j'ai débarqué sur le sujet du "rendu monnaie" sans rien regarder sur ce qui avait été écrit déjà sur le sujet, et je m'aperçois que c'est un problème assez général.

---

Ce qui fait que le problème est NP-complet, c'est sa complexité exponentielle.

Dans le cas où on travaille sur un nombre fini de N éléments, "calculer toutes les solutions et choisir parmi les meilleures" fonctionnera tant qu'on a le temps et les ressources physiques.

Par contre, la question initiale était de trouver un algorithme optimal de rendu de monnaie. Ça existe lorsqu'on a un système monétaire canonique (et c'est la définition du "canonique") mais, dans le cas général, on bricole en espérant que le fond de caisse soit "petit" (car çà va prendre du temps).

- W