Discussion :

[Linkau]

Hey tout le monde ^^,

Pour un projet je dois écrire une fonction qui prend en paramètres une liste de pièces unique (ex : [4,3,3,1,1]) et un montant (ex:6) et renvoie la liste des pièces utilisés.

Du coup pour l'instant j'ai réussis à faire l'aglo glouton mais pour l'optimal je galère un peu plus (ex: pour l'instant pour la liste d'avant je trouvais la liste [4,1,1] alors qu'il faudrait trouver [3,3])

Voila pour mon problème si vous avez des questions

Merci d'avance pour vos réponses

[charliemtx]

Bonjour,

Pouvez-vous joindre le code que vous avez déjà fait pour que l'on puisse vous aiguiller au mieux ?

[Linkau]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
def rendreMonnaieGlouton(n, s):
    ret = []
 
    if n == 0:
        return ret
    if len(s) == 0:
        return None
 
    sbis = list(s)
    while len(sbis) != 0:
        #on prend la valeur la plus grande du tableau
        maxVal = max(sbis)
        iMaxVal = s.index(maxVal)
 
        sbis.remove(maxVal)
        p = s.pop(iMaxVal)
 
        if p == n:
            ret.append(p)
            s.append(p)
            return ret
        else:
            if p > n:
                s.append(p)
                continue
            else:
                ret.append(p)
                res = rendreMonnaieGlouton(n-p, s)
                s.append(p)
                if res != None:
                    for x in res:
                        ret.append(x)
                    return ret
                else :
                    return None
    return None

Voila pour l'algo glouton après il y a surement bien plus simple ^^'

[charliemtx]

1) Etant donné que la fonction doit retourner une liste, j'aurais retourné des [] à la place des None (c'est pinaillage) ; j'aurais également ajouté (par exemple) à la places None (quand le total demandé est 0, ou inférieur à la plus petite des pièces existante) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

raise ValueError :

2) La boucle indexée sur la longueur de sbis me semble étrange... je pense qu'il faut tout refaire, ne serait-ce parce qu'il y a une erreur de raisonnement dans le fait de forcément prendre la plus haute valeur en pièces dans le rendu final ; votre exemple en est la preuve.
Je crois qu'il faut essayer avec toutes les valeurs de pièces, la meilleure combinaison composée de pièces de valeur inférieur ; parmi toutes ces combinaisons, retourner celle qui a le plus petit nombre d'éléments

[lg_53]

On peut faire un algo qui est celui que la boulangère applique lorsqu'elle nous rend la monnaie. Ca va nous donner une solution au problème "je donne quoi comme pièces pour faire X euros".

Maintenant ce que vous introduisez dans votre question, c'est le mot "optimal". Ca veut dire quoi optimal ? Il faut préciser, car ca peut être optimal selon plein de critère différent !

Bon là de ce que je devine, optimal voudrait dire avec le moins de pièces possibles. Mais du coup ca reste une optimisation. Donc soit vous adoptez :
- un algorithme qui va parcourir exhaustivement toutes les solutions pour identifier à cout sûr la meilleure
- un qui va ne faire qu'un nombre limité d'évaluation, mais qui va vous sortir une solution qui sera seulement localement optimale. Ca veut dire que si vous modifier un peu la solution, alors vous aurez forcément une solution moins bonne. Mais ca ne veut pas dire qu'il n'existe pas de meilleures solutions que celle trouvée, solution qui pourrait etre radicalement différente.

Là au vu de la taille de votre problème, ce n'est pas très couteux d'examiner toutes les possibilités.
Vous les examiner toutes, ne retenez que celles qui sont solutions (à mettre dans une liste par exemple), et après sur cette liste, vous identifier la possibilité la plus courte (i.e. avec le moins de pièces).

Et après, à vous de voir :
1) qu'est ce qu'on retourne s'il y a plusieurs solutions avec le meme nombre pieces ?
2) qu'est ce qu'on fait s'il n'y a pas de solutions ? Comment détecter ca ?
3) est ce qu'on traite les 2 questions précédentes, ou est ce qu'on suppose que ce qui est donné à la fonction admet une solution, et que celle-ci est unique ? (chose que mathématiques on fait souvent, mais informatiquement ce n'est en général pas une bonne idée)

[Sve@r]

Salut

Du coup pour l'instant j'ai réussis à faire l'aglo glouton

Désolé, ton algo ne fonctionne pas si on entre 6 avec [4, 3, 3, 1]. En prenant la pièce la plus grosse (ici 4) tu entres dans un cul de sac.
Il te faut partir sur l'idée de lg_53, à savoir calculer toutes les solutions et ensuite extraire 1) celle qui donne un résultat et éventuellement 2) celle qui correspond à l'idée que tu te fais d'une optimisation.

Voila pour l'algo glouton après il y a surement bien plus simple ^^'

Ca peut se faire...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import itertools
 
def rendreMonnaie(n, s):
	yield from sorted(
		set(
			y for y in (
				x\
				for i in range(1, len(s) + 1)\
				for x in itertools.combinations(s, i)
			) if sum(y) == n
		),
		key=lambda x: len(x),
	)
# rendreMonnaie()
 
for m in rendreMonnaie(6, [4, 3, 3, 3, 1, 1, 6]):
	print(m)

[marco056]

Houmpff ! Même après qqs années de pratique, je n'y comprends rien : pas à la portée du premier débutant venu

[Sve@r]

Houmpff ! Même après qqs années de pratique, je n'y comprends rien : pas à la portée du premier débutant venu

Réécris la comprehension list sous forme de boucle standard

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for i in range(1, len(s) + 1):
	for x in itertools.combinations(s, i):
		print(x)

C'est de là que je suis parti. Donc de là tu verras le principe utilisé et pourras en déduire le reste

[marco056]

Oui, enfin avec des set, yield et autres sorted(key lambda) c'est quand même du haut niveau.
J'ai des choses à comprendre bien avant cela.

[charliemtx]

Oui, enfin avec des set, yield et autres sorted(key lambda) c'est quand même du haut niveau.

Et non justement ! Ce sont des fondamentaux. Le bon niveau c'est au minimum de comprendre à quoi servent ses fonctions, le haut niveau c'est savoir quand les utiliser intelligemment

J'ai des choses à comprendre bien avant cela.

Je dirai au contraire que ça vaut le coup de prendre quelques minutes, ou quelques heures selon votre niveau, de comprendre ces notions ; un exemple tout bête : moi-même.
Je suis un pur autodidacte et j'ai commencé au travers de ma formation à la fac avec Matlab. Quand j'ai commencé à coder en python, je ne jurai que par le module NumPy et ses arrays... sans même connaître les listes ! Lorsque j'ai commencé à creuser, je me suis rendu compte de tout le boulot que j'avais pour rien avec mes arrays

[marco056]

Et non justement ! Ce sont des fondamentaux. Le bon niveau c'est au minimum de comprendre à quoi servent ses fonctions, le haut niveau c'est savoir quand les utiliser intelligemment



Je dirai au contraire que ça vaut le coup de prendre quelques minutes, ou quelques heures selon votre niveau, de comprendre ces notions ; un exemple tout bête : moi-même.
Je suis un pur autodidacte et j'ai commencé au travers de ma formation à la fac avec Matlab. Quand j'ai commencé à coder en python, je ne jurai que par le module NumPy et ses arrays... sans même connaître les listes ! Lorsque j'ai commencé à creuser, je me suis rendu compte de tout le boulot que j'avais pour rien avec mes arrays

Disons que dans mon boulot, je n'en ai pas besoin et que pour les loisirs, j'ai d'autres occupations.
J'aime bien creuser et je le ferai sans doute si j'ai le temps, pourquoi pas cet été ?

[Linkau]

Whoaah, merci pour toutes vos réponses je vais essayer de les analyser et je reviendrais vers vous si j'ai des questions

[tyrtamos]

Bonjour,

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.

Ma solution est moins élégante que celle de Sve@r (waouh...), mais je la comprends beaucoup mieux...

Son principe est simple:
- la structure de la caisse est celle-ci pour reprendre l'exemple du PO: C = [[4, 1], [3, 2],[1, 2]]. J'ai donc 1 pièce de 4€ (qui n'existe pas), 2 pièces de 3€ (pareil), et 2 pièces de 1€
- pour rendre la monnaie sur 6€, par exemple, l'algorithme commence à 4€ et cherche à atteindre le rendu exact en prenant le plus de pièces de plus forte valeur.
- bien sûr, dans ces essais, il faudra revenir en arrière quand on arrive à des résultats trop forts. Par exemple, 4€+3€=7: trop fort pour 6€ => on annule le dernier 3€ et on recommence avec 1€.
- en faisant comme ça, on trouve la 1ère solution [4, 1, 1]
- S'il y a une solution, l'algorithme en cherche une autre, en commençant cette fois par la pièce plus petite que 4€: 3€. Et on trouve une 2ème solution: [3, 3]
- à la fin, on cherche la meilleure solution en les triant selon le nombre de pièces rendues, et on prend la solution ayant le moins de pièces. Ici, ce sera: [3, 3]

Voilà la fonction largement commentée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def rendumonnaie(C=[], arendre=0):
    """Rendre la monnaie
       - C: argent en caisse. Ex: C[..., [2, 5], ...] => 5 pièces de 2€
       - arendre: valeur pour la monnaie à rendre
       Retourne la liste des pièces à rendre
    """
    if arendre > sum([p*n for p, n in C]) or arendre < C[-1][0]:
        yield [] # arendre trop grand ou trop petit: impossible
 
    M = [] # future liste de la monnaie à rendre
 
    ic0 = 0 # indice de départ de la pièce dans la caisse
    while C[ic0][0] > arendre:
        ic0 += 1 # on ne commence pas avec 2€ pour rendre la monnaie sur 1€!
 
    ic = ic0 # indice en cours de la pièce dans la caisse C
    jc = 0# indice en cours de la pièce en fonction du nb de pièces
    v = 0 # valeur du rendu en cours
    while True:
        # tentative d'ajout de la pièce en cours ic
        v += C[ic][0]
        M.append(C[ic][0])
        if v == arendre:
            # on a une solution
            yield  M
            # recherche d'une autre solution en démarrant à la pièce suivante
            ic0 += 1
            if ic0 > len(C)-1:
                break # Pas d'autre solution
            ic = ic0
            jc = 0
            M = []
            v = 0
        elif v > arendre:
            # on ne peut pas rendre trop: retour en arrière
            # annulation dernier ajout
            v -= C[ic][0] 
            M.pop(-1)
            # prendre plus petit si c'est possible
            ic += 1 # pièce suivante plus petite
            jc = 0 # 1er indice de cette pièce
            if ic > len(C)-1:
                # plus de pièce à essayer => pas de solution
                break
        else: 
            # v < arendre: on n'a pas encore atteint la somme à rendre
            # préparer l'ajout d'une autre même pièce'il y en a encore
            jc += 1
            if jc > C[ic][1]-1:
                # on a plus de pièce de cette valeur
                ic += 1 # pièce suivante plus petite
                jc = 0 # 1er indice de cette piècee
                if ic > len(C)-1:
                    # plus de pièce à essayer => pas de solution
                    break 
    yield []

Application pour l'exemple du PO:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C =  [[4, 1], [3, 2],[1, 2]]
arendre = 6
 
R = [] # liste des solutions
print("à rendre=", arendre)
for M in rendumonnaie(C, arendre):
    if len(M) > 0:
        print("Solution:", M)
        R.append(M)
if len(R)==0:
    print("Aucune solution")
else:    
    print()
    MS = sorted(R, key=lambda v: len(v))[0]
    print("Meilleure solution:", MS)

Ce qui donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
à rendre= 6
Solution: [4, 1, 1]
Solution: [3, 3]
 
Meilleure solution: [3, 3]

On peut tester des solutions plus complexes. Par exemple, une caisse plus fournie (on raisonne en centimes ici):
C = [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]

On voit que comme on n'a pas de 1 centimes, il y aura des valeurs à rendre impossibles.

Et on peut tester l'algorithme sur toutes les valeurs à rendre, entre les limites:
C[-1][0] puisqu'on ne peut pas espérer rendre la monnaie sur 1 centimes quand la caisse n'en comporte pas. Ici, ce sera 2.
sum([p*n for p, n in C]) puisqu'on ne peut pas rendre la monnaie sur une somme qui dépasse la valeur totale de la caisse. Ici, ce sera 2870.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
C =  [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]
 
for arendre in range(C[-1][0], sum([p*n for p, n in C])+1):
    R = [] # liste des solutions pour arendre
    print("="*80)
    print("à rendre=", arendre)
    for M in rendumonnaie(C, arendre):
        if len(M) > 0:
            print("Solution:", M)
            R.append(M)
    if len(R)==0:
        print("Aucune solution")
    else:    
        print()
        MS = sorted(R, key=lambda v: len(v))[0]
        print("Meilleure solution:", MS)

Pour cette caisse, on trouve par exemple des solutions comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
 
================================================================================
à rendre= 10
Solution: [10]
Solution: [5, 5]
Solution: [2, 2, 2, 2, 2]
 
Meilleure solution: [10]
================================================================================
à rendre= 11
Aucune solution
================================================================================
à rendre= 12
Solution: [10, 2]
Solution: [5, 5, 2]
 
Meilleure solution: [10, 2]
 
...
 
================================================================================
à rendre= 351
Aucune solution
================================================================================
à rendre= 352
Solution: [200, 100, 50, 2]
Solution: [100, 100, 100, 50, 2]
Solution: [50, 50, 50, 50, 50, 50, 50, 2]
Solution: [20, 20, 20, 20, 20, 20, 20, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 2]
 
Meilleure solution: [200, 100, 50, 2]
 
...

Même pour des caisses assez complexes, cet algorithme est très rapide. Je crois que l'on trouve toutes les solutions, mais je ne l'ai pas vérifié (il faudrait calculer toutes les combinaisons possibles).

En tout cas, c'était très amusant à faire: merci au PO Linkau!

[Sve@r]

Même pour des caisses assez complexes, cet algorithme est très rapide. Je crois que l'on trouve toutes les solutions

Ben malheureusement non. Comme pour Linkau ton algorithme ne fonctionne pas si on entre 4, 3, 3, 1 (ou dans ta notation (4, 1), (3, 2), (1, 1)) avec à rendre 6. Là où n'importe quelle boulangère rendra 3+3, ton algo s'est focalisé sur 4 puis n'a pas su surmonter l'erreur. Toutefois (chose bizarre) en entrant (4, 1), (3, 2), (1, 2) là il a trouvé 4+1+1 et aussi 3+3.

[wiztricks]

On peut tester des solutions plus complexes. Par exemple, une caisse plus fournie (on raisonne en centimes ici):
C = [[200, 5], [100, 5], [50, 20], [20, 7], [10, 12], [5, 20], [2, 5]]

Avec le système de monnaie de l'euro, la première solution trouvée par l'algorithme glouton sera optimale (côté nombre de pièces): c'est un système canonique.

Sinon dans le cas général, c'est un problème NP-complet (il n'existe pas d'algo optimal).

- W

[tyrtamos]

Bonjour

Ben malheureusement non. Comme pour Linkau ton algorithme ne fonctionne pas si on entre 4, 3, 3, 1 (ou dans ta notation (4, 1), (3, 2), (1, 1)) avec à rendre 6. Là où n'importe quelle boulangère rendra 3+3, ton algo s'est focalisé sur 4 puis n'a pas su surmonter l'erreur. Toutefois (chose bizarre) en entrant (4, 1), (3, 2), (1, 2) là il a trouvé 4+1+1 et aussi 3+3.

Pas d'accord! Il n'est pas dit que la meilleure solution devrait être la 1ère trouvée (même si c'est fréquent)! Et dans l'exemple du PO, la solution [3,3] n'a pas été trouvée par hasard, mais grâce à l'algorithme, et j'ai expliqué comment.


De wiztricks:

Sinon dans le cas général, c'est un problème NP-complet (il n'existe pas d'algo optimal)

Merci, je ne savais pas. Et heureusement, parce que je n'aurais peut-être pas commencé .

[Sve@r]

Pas d'accord! Il n'est pas dit que la meilleure solution devrait être la 1ère trouvée (même si c'est fréquent)! Et dans l'exemple du PO, la solution [3,3] n'a pas été trouvée par hasard, mais grâce à l'algorithme, et j'ai expliqué comment.

Tu n'as pas bien compris: ton programme ne fonctionne pas si on lui demande de trouver 6 avec les pièces 4, 3, 3 et 1. Dans ce cas il retourne une liste vide.

[tyrtamos]

Tu n'as pas bien compris: ton programme ne fonctionne pas si on lui demande de trouver 6 avec les pièces 4, 3, 3 et 1. Dans ce cas il retourne une liste vide.

Chez moi, il fonctionne parfaitement, et les résultats que j'ai mis dans mon message sont un simple copier-coller des résultats.

Avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
C =  [[4, 1], [3, 2],[1, 2]]
arendre = 6

(attention: tu dis [4,3,3,1] mais c'est [4,3,3,1,1])

et le petit code d'appel que j'ai donné, ça affiche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
à rendre= 6
Solution: [4, 1, 1]
Solution: [3, 3]
 
Meilleure solution: [3, 3]

Il faut trouver pourquoi ça ne marche pas chez toi. Chez moi: Python 3.7.8 sur Windows 10.

[Sve@r]

(attention: tu dis [4,3,3,1] mais c'est [4,3,3,1,1])

Justement, c'est bel et bien 4, 3, 3 et 1 (4 pièces dont une seule de 1) que je lui passe. Comme l'algorithme glouton de Linkau ne pouvait pas fonctionner avec cette configuration (cf mon premier post), j'ai voulu aussi la tester sur ton code.

[tyrtamos]

Justement, c'est bel et bien 4, 3, 3 et 1 (4 pièces dont une seule de 1) que je lui passe. Comme l'algorithme glouton de Linkau ne pouvait pas fonctionner avec cette configuration (cf mon premier post), j'ai voulu aussi la tester sur ton code.

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.

La raison est la suivante.
- au départ, je commence par ic0=4€, et je cherche jusqu'à ce que la dernière pièce soit essayée.
- s'il n'y a pas de solution, ça retourne [].
- Il faut après essayer en partant de ic0=3€ (la pièce suivante), mais mon code précédent n'engageait cette possibilité que si la 1ère tentative était réussie! Ce qui était une erreur manifestement. Maintenant, on cherche jusqu'à ce que ic0 arrive à la dernière pièce et pas seulement ic.

Maintenant, avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
C =  [[4, 1], [3, 2],[1, 1]]
arendre = 6

ça donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
à rendre= 6
Solution: [3, 3]
 
Meilleure solution: [3, 3]

Voilà le code corrigé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from operator import itemgetter 
 
def rendumonnaie(C=[], arendre=0):
    """Rendre la monnaie
       - C: argent en caisse. Ex: C[..., [2, 5], ...] => 5 pièces de 2€
       ' arendre: valeur de la monnaie à rendre
       Retourne la liste des pièces à rendre
    """
    # Etre sûr que les valeurs de la caisse sont dans le bon ordre
    C.sort(key=itemgetter(0), reverse=True)
 
    if arendre > sum(p*n for p, n in C) or arendre < C[-1][0]:
        yield [] # arendre trop grand ou trop petit: impossible
 
    M = [] # future liste de la monnaie à rendre
 
    ic0 = 0 # indice de départ de la pièce dans la caisse
    while C[ic0][0] > arendre:
        ic0 += 1 # on ne commence pas avec 2€ pour rendre la monnaie sur 1€!
 
    ic = ic0 # indice en cours de la pièce dans la caisse C
    jc = 0# indice en cours de la pièce en fonction du nb de pièces
    v = 0 # valeur du rendu en cours
    while True:
        # tentative d'ajout de la pièce en cours ic
        v += C[ic][0]
        M.append(C[ic][0])
        if v == arendre:
            # on a une solution
            yield  M
            # recherche d'une autre solution en démarrant à la pièce suivante
            ic0 += 1
            if ic0 > len(C)-1:
                break # => on a fini
            ic = ic0
            jc = 0
            M = []
            v = 0
        elif v > arendre:
            # on ne peut pas rendre trop: retour en arrière
            # annulation dernier ajout
            v -= C[ic][0] 
            M.pop(-1)
            # prendre plus petit si c'est possible
            ic += 1 # pièce suivante plus petite
            jc = 0 # 1er indice de cette pièce
            if ic > len(C)-1:
                # fin de cet essai
                # recherche d'une autre solution en démarrant à la pièce suivante
                ic0 += 1
                if ic0 > len(C)-1:
                    break # => on a fini
                ic = ic0
                jc = 0
                M = []
                v = 0
        else: 
            # v < arendre: on n'a pas encore atteint la somme à rendre
            # préparer l'ajout d'une autre même pièce'il y en a encore
            jc += 1
            if jc > C[ic][1]-1:
                # on a plus de pièce de cette valeur
                ic += 1 # pièce suivante plus petite
                jc = 0 # 1er indice de cette piècee
                if ic > len(C)-1:
                    # fin de cet essai
                    # recherche d'une autre solution en démarrant à la pièce suivante
                    ic0 += 1
                    if ic0 > len(C)-1:
                        break # => on a fini
                    ic = ic0
                    jc = 0
                    M = []
                    v = 0
    yield []

Merci pour ta remarque!

[Edit]: deux petites améliorations du code sans conséquence sur les résultats: ajout d'un tri de C au début de la fonction (+ importation de itemgetter), et modification de l'argument de sum(): remplacement d'une list compréhension par un générateur.