Discussion :

[lirgon]

Mon problème est la généralisation du problème de monnaie :

soit a+4b+6c=8. Objectif : Min a+b+c

Le système admet une solution car pgcd (1,4,6) divise 8.

Donc déjà ,il faudrait que je calcule de pgcd de trois nombres,(deux j'y arrive mais pas trois )

Ensuite,par l'algorithme de Glouton, la solution serait (a,b,c)=(2,0,1).
Or la solution optimale erait (a,b,c)=(0,2,0). Car 0+2+0<2+0+1

Qui pourrait mieux faire que l'algorithme de Glouton,

Merci d'avance

[souviron34]

on n'est pas un site de concours.. Si tu veux ça, il y a la rubrique défis...

[lirgon]

ce n'est pas un test ni un concours....

j'ai réussi à implémenter l'algorithme de Glouton,mais je me demande s'il y'a un moyen de résoudre ce problème avec une solution optimale pour tous les cas...

Si certains pourraient me donner quelques piste de réflexion, ou quelques indices...

par exemple:

2a+3b+4c=9 ; solution optimale (a,b,c)=(0,3,0) / Solution Glouton (0,0,2) + reste 1

a+2b+3c=7 ; solution solution optimale(a,b,c)=(1,0,2) / Solution Glouton (1,0,2)

a+4b+5c=12 ; solution optimale (a,b,c)=(0,3,0) / Solution Glouton (2,0,2)

[Zavonen]

Donc déjà ,il faudrait que je calcule de pgcd de trois nombres,(deux j'y arrive mais pas trois

pgcd(a,b,c)=pgcd(a,pgcd(b,c))