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