Choix optimal des pièces de monnaie - Lycée Żmichowska (Varsovie)

Pour chaque ensemble de pièces de monnaie à valeur nominale 1, 2, 3 … on peut déterminer le montant le plus élevé S tel que l’on peut payer chaque somme de 1 à S en n'utilisant que des pièces de monnaie de l’ensemble. On suppose que l’on a dans notre porte-monnaie k pièces de monnaie et on se pose la question comment choisir les nominaux pour pouvoir payer le montant S(k) le plus élevé.