Bon déjà, l'énoncé est mal posé:
L'algo glouton doit il être optimal pour toute somme possible, ou bien pour un ensemble de valeurs somme cibles déterminé?
Dans le premier cas, 1 doit obligatoirement faire partie des valeurs des pièces, et dans le second, je n'ai aucune idée de l'existence d'un critère général .
Si on suppose qu'on est dans le premier cas, intuitivement, je dirais que si on a une suite dans laquelle pour toute succession de 3 valeurs consécutives, 1 < a < b < c, on a a+c = 2b, alors l'algo glouton devrait être optimal, mais c'est clairement pas une condition nécessaire, car les suites (1, k, k^2, k^3, ..., k^N) sont elles aussi avec un algo glouton optimal il me semble.
J'ai l'impression que les suites dans laquelle pour toute succession de 2 valeurs consécutives, 1 < a < b on a b <= 2*a sont elles aussi avec un algo glouton optimal.
A+,
---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --